#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int x,int y)
{
    return x > y;
}
int a[1000100];
int g[1000100];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int sz = 0;
    for (int i = 1; i <= n; i++) 
    {
        int pos = upper_bound(g+1,g+sz+1,a[i],cmp) - g;
        g[pos] = a[i];
        sz = max(sz,pos);
    }
    cout << sz << endl;
    sz = 0;
    for (int i = 1; i <= n; i++) 
    {
        int pos = lower_bound(g+1,g+sz+1,a[i]) - g;
        g[pos] = a[i];
        sz = max(sz,pos);
    }
    cout << sz;
    return 0;
}