#include<bits/stdc++.h>
using namespace std;

int dp[100001],n,a[100001],l,r,mid,rr,k,kk;

int main(){
	//n=10;
	memset(dp,0,sizeof(dp));
	//for(int i=1;i<=n;i++)cin>>a[i];
	while(~scanf("%d",&a[++n])); --n;
	dp[1]=a[1],rr=1;
	for(int i=2;i<=n;i++){
		l=1;r=rr;
		while(l<r){
			mid=(l+r)/2;
			if(dp[mid]>=a[i])r=mid;
			else if(dp[mid]<a[i])l=mid+1;
		}
		if(l==rr&&dp[l]<=a[i])rr++,dp[rr]=a[i];
		else if(l==rr&&dp[l]>a[i])dp[l]=a[i];
		else dp[l]=a[i];
	}
	k=rr;
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n/2;i++)swap(a[i],a[n+1-i]);
	dp[1]=a[1],rr=1;
	for(int i=2;i<=n;i++){
		l=1;r=rr;
		while(l<r){
			mid=(l+r)/2;
			if(dp[mid]>=a[i])r=mid;
			else if(dp[mid]<a[i])l=mid+1;
		}
		if(l==rr&&dp[l]<=a[i])rr++,dp[rr]=a[i];
		else if(l==rr&&dp[l]>a[i])dp[l]=a[i];
		else if(dp[l]!=a[i])dp[l]=a[i];
		else {
			   if(a[i]==dp[l])l++;dp[l]=a[i];
		}
	}
	kk=rr;
	cout<<kk<<endl<<k;
	return 0;
}