#include <bits/stdc++.h>
using namespace std;
long long n,mid,l,r;
long long maxn,total=0,a[50010],b[50010];
int main(){
	while(scanf("%d",&a[++n])!=EOF); 
	n--;
	for(long long i=1;i<=n;i++){
		l=0; r=total;
		while(l<r){
			mid=(l+r+1)>>1;
			if(a[i]>b[mid]){r=mid-1;}
			else {l=mid;}
		}
		total=max(total,r+1);
		b[r+1]=a[i];
	}
	printf("%lld\n",total);
	memset(b,0,sizeof(b)); total=0;
	for(long long i=1;i<=n;i++){
		l=0; r=total;
		while(l<r){
			mid=(l+r+1)>>1;
			if(a[i]<=b[mid]){r=mid-1;}
			else {l=mid;}
		}
		total=max(total,r+1);
		b[r+1]=a[i];
	} 
	printf("%lld\n",total);
	return 0;
}