#include<iostream>
#include<algorithm>
using namespace std;
int n,a[100005],dp[100005],num,ans,en[100005],cnt;
int main(){
	while(cin>>a[++n]) a[n]=-a[n];
	n--;
	dp[1]=a[1];	
	for(int i=1;i<=n;i++){
		num=lower_bound(dp+1,dp+num+1,a[i])-dp;
		dp[num]=a[i];
		ans=max(ans,num);
	}
	cout<<ans<<endl;
	for(int i=1;i<=n;i++) a[i]=-a[i];
	for(int i=1;i<=n;i++){
		if(en[cnt]<a[i]) {
			en[++cnt]=a[i];
		}
		else {
			int j=lower_bound(en+1,en+cnt+1,a[i])-en;
			en[j]=a[i];
		}
	}
	cout<<cnt;
	return 0;
}