rt

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,a[114514],dp[114514],len[114514],t1,m;
bool cmp(int qw,int er)
{
	return qw>er;
}//比较函数
signed main()
{
	len[0]=1145141919810;
	/*while(cin>>t1)
		a[++n]=t1;*/
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
	}//此处为输入方便，上面注释的是交上去的输入
	for(int i=1;i<=n;++i)
	{
		t1=lower_bound(len,len+m,a[i],cmp)-len;
        //t1为临时变量，下同
		dp[i]=t1+1;
		len[t1+1]=max(a[i],len[t1+1]);
		m=max(m,t1+1);//m为len的长度，下同
	}
	printf("%lld\n",m);
	memset(len,0,sizeof(len));
	m=1;
	len[1]=a[1];
	for(int i=2;i<=n;++i)
	{
		t1=lower_bound(len+1,len+m+1,a[i])-len;
		if(a[i]>len[t1])
		{
			m++;
			len[m]=a[i];
		}
		else
		{
			len[t1]=a[i];
		}
	}
	printf("%lld",m);
	return 0;
}