#include<bits/stdc++.h>
#define int long long 
using namespace std;
int arr[100005],i,dp[100005],cnt,dps[100005];
signed main(){
	dp[0]=50001;
	while(cin>>arr[++i]){
		if(arr[i]<dp[cnt]){
			dp[++cnt]=arr[i];
			continue;
		}
		int l=1,r=cnt,ans;
		while(l<=r){
			int mid=(l+r)/2;
			if(dp[mid]<=arr[i]){
				r=mid-1;
				ans=mid;
			}
			else l=mid+1;
		}
		dp[ans]=arr[i];
	}
	cout<<cnt<<endl;
	cnt=0;
	for(int j=1;j<=i;j++){
		if(arr[j]>dps[cnt]){
			dps[++cnt]=arr[j];
			continue;
		}
		int l=1,r=cnt,ans;
		while(l<=r){
			int mid=(l+r)/2;
			if(dps[mid]>=arr[j]){
				r=mid-1;
				ans=mid;
			}
			else l=mid+1;
		}
		dps[ans]=arr[j];
	}
	cout<<cnt;
	return 0;
}