#include<bits/stdc++.h>
using namespace std;
int n=1,ans1=1,ans2=1,cnt,a[100005],len[100005];
int main(){
//	freopen("daodan.in","r",stdin);
//	freopen("daodan.out","w",stdout);
	memset(len,0x3f,sizeof len);
	while(cin>>a[n])
		n++;
	n--;
	len[n]=a[n];
	for(int i=n-1; i>=1; i--)
	{
		int p=upper_bound(len+1,len+n+1,a[i])-len;
		if(p==n+1)
		{
			len[1]=min(len[1],a[i]);
			continue;
		}
		len[p]=a[i];
		ans1=ans1<p?ans1+1:ans1;
	}
	memset(len,0x3f,sizeof len);
	len[1]=a[1];
	for(int i=2; i<=n; i++)
	{
		int p=lower_bound(len+1,len+n+1,a[i])-len;
		if(p==n+1)
		{
			len[1]=min(len[1],a[i]);
			continue;
		}
		len[p]=a[i];
		ans2=ans2<p?ans2+1:ans2;
	}
	printf("%d\n%d",ans1,ans2);
    return 0;
}