#include<bits/stdc++.h>
using namespace std;
const int N = 100005;

int n;
int a[N],b[N],c[N];

bool cmp(const int &a,const int &b)//加速 and 避免手贱 
{
	return a>b;
}

int main()
{
	while(cin>>a[++n]);//记录输入数的数量 
	n--;//因为从 1 开始，所以要减一 
	int len1=1,len2=1;
	// len1 : 表示这套系统最多能拦截多少导弹 
	// len2 : 表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统 
	b[1]=a[1];//求不上升序列长度 
	c[1]=a[1];//用于求上升序列长度 
	// cout<<b[1]<<" "; 
	// cout<<c[1]<<" ";
	for(int i=2;i<=n;i++)
	{
		if(b[len1]>=a[i])
			b[++len1]=a[i];//如果满足要求(不上升)就加入d1，len1++ 
		else
		{
			int p1=upper_bound(b+1,b+1+len1,a[i],cmp)-b;//获取 p1 的值 
			b[p1]=a[i];
		}//否则用a[i]替换d1中的一个数 
		// cout<<b[len1]<<" ";
		if(c[len2]<a[i])
			c[++len2]=a[i];
		else
		{
			int p2=lower_bound(c+1,c+1+len2,a[i])-c;//获取 p2 的值 
			c[p2]=a[i];
		}//同上 
		// cout<<c[len2]<<" ";
	}
	// cout<<endl;
	cout<<len1<<endl<<len2;//完结散花 
	return 0;
}