QwQ,rt

#include<bits/stdc++.h>
using namespace std;
int a[100010],dp[100010],n,ans; 
int main(){
	int x;
	while(cin>>x)
	    a[n++]=x;
	n=n-1;
	dp[0]=0x7ffffff;
	for(int i=1;i<=n;i++){
		int l=0,r=i,k=a[i];
		ans=0;
		while(l<r){
			int mid=(l+r)/2;
			if(dp[mid]>=k)
			    l=mid+1;
			else{
				ans=mid;
				l=mid-1;
			}
		}
		dp[ans]=k;
	}
	int num;
	for(num=1;num<=n;num++){
		if(dp[num]==0) break;
	}
	cout<<num-1<<endl;
	dp[0]=0;
	for(int i=1;i<=n;i++)
	    dp[i]=0x7fffffff;
	for(int i=1;i<=n;i++){
		int l=0,r=i,k=a[i];
		while(l<r){
			int mid=(l+r)/2;
			if(dp[mid]<k)
			    l=mid+1;
			else{
				ans=mid;
				r=mid-1;
			}
		}
	}
	for(num=0;num<=n;num++){
		if(dp[num]==0x7fffffff)
		    break; 
	}
	cout<<num-1;
	return 0;
}