#include<bits/stdc++.h>
using namespace std;
int a[100010],n,b[100010],c[100010],m,k;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    b[0]=-2147483647;
    for(int i=1;i<=n;i++)
    {
        if(-a[i]>=b[m]) b[++m]=-a[i];
        else{
            int x=upper_bound(b+1,b+m+1,-a[i])-b;
            b[x]=-a[i];
        }
        if(a[i]>c[k]) c[++k]=a[i];
        else
        {
            int x=lower_bound(c+1,c+k+1,a[i])-c;
            c[x]=a[i];
        }
    }
    printf("%d\n%d",m,k);
    return 0;
}