#include<iostream>

#include<cstdio>

using namespace std;

int d,b[100005],c[100005],n,len1,len2,mx;

int que(int x)

{

	int ret=0;

	for(;x<=mx;x+=x&-x)

		ret=max(ret,b[x]);

	return ret;

}

void add(int x,int w)

{

	for(;x>0;x-=x&-x)

		b[x]=max(b[x],w);

}

int main()

{

	while(scanf("%d",&d)==1)

	{

		mx=max(mx,d);

//		if(!len1||d<=b[len1])b[++len1]=d;

//		else

//		{

//			for(int i=len1;i>=0;i--)

//				if(d<=b[i]||(i==0&&d>b[1]))

//				{

//					b[i+1]=d;

//					break;

//				}

//		}

		int k=que(d);

		add(d,k+1);

		if(d>c[len2])c[++len2]=d;

		else

		{

			int k=lower_bound(c+1,c+len2+1,d)-c;

			c[k]=d;

		}

	}

	for(int i=1;i<=mx;i++)

		len1=max(len1,b[i]);

	printf("%d\n%d",len1,len2);

	return 0;

}