#include<bits/stdc++.h>
using namespace std;
long long a[50000],dp[50000],zx;
int n,len,minbh;
bool f;
int main(){
	while(scanf("%d",a+n))
		++n;
	for(int i=0;i<n;++i){
		if(!i)
			dp[len++]=a[0];
		else{
			if(a[i]<=dp[len-1])
				dp[len++]=a[i];
			else
				for(int j=0;j<len;++j){
					if(a[i]>dp[j]&&j==0){
						dp[j]=a[i];
						break;
					}
					else if(j!=0&&a[i]>dp[j]&&a[i]<=dp[j-1]){
						dp[j]=a[i];
						break;
					}
				}
		}
	}
	printf("%d",len);
	putchar('\n');
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;++i){
		if(!i){
			dp[0]=a[0];
			len=1;
		}
		else{
			zx=INT_MAX,f=false;
			for(int j=0;j<len;++j)
				if(dp[j]<zx&&dp[j]>=a[i]){
					zx=dp[j];
					minbh=j;
					f=true;
				}
			if(f)
				dp[minbh]=a[i];
			else
				dp[len++]=a[i];
		}
	}
	printf("%d",len);
	return 0;
}