#include<cstdio>
#include<cstring>
int max(int a,int b){return a>b?a:b;}
int n,a[100001],dp[100001]={0x7fffffff},len;
void search(int x){
	int l=1,r=len;
	while(l<=r){
		int mid=((r-l)>>1)+l;
		if(dp[mid]<=x && dp[mid-1]>x){
			dp[mid]=x;
			return;
		}
		if(dp[mid]<x) r=mid-1;
		else l=mid+1;
	}
}
void search2(int x){
	int l=1,r=len;
	while(l<=r){
		int mid=((r-l)>>1)+l;
		if(dp[mid]>x && dp[mid-1]<x){
			dp[mid]=x;
			return;
		}
		if(dp[mid]>x) r=mid-1;
		else l=mid+1;
	}
}
int main(){
	while(scanf("%d",&a[++n])!=EOF);
	n--;
//	printf("%d",dp[1]);
//	printf(" %d \n",n);
	for(int i=1;i<=n;i++){
		if(a[i]<=dp[len]) dp[++len]=a[i];
		else search(a[i]);
	}
//	for(int i=1;i<=len;i++) printf("%d ",dp[i]);
	printf("%d\n",len);
	len=0;
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		if(dp[len]<a[i]) dp[++len]=a[i];
		else search2(a[i]);
	}
	printf("%d",len);
	return 0;
}