#include<bits/stdc++.h>
using namespace std;
inline int max(const int &q,const int &w){
	return q>w?q:w;
}
const int M=1e5+5;
int n,l,r,mid,a[M],q[M],h[M],t;
int main(){
	while(scanf("%d",&a[++n])!=EOF);
	q[0]=INT_MAX;
	for(int i=1;i<=n;++i){
		if(a[i]<=q[t])q[++t]=a[i];
		else{
			l=1,r=t;
			while(l<r){
				mid=l+r>>1;
				if(q[mid]>=a[i])l=mid+1;
				else r=mid;
			} 
			q[r]=a[i];
		}
	}
	printf("%d\n",t-1);
	t=0;
	for(int i=1;i<=n;++i){
		if(a[i]>h[t])h[++t]=a[i];
		else{
			l=1,r=t;
			while(l<r){
				mid=l+r>>1;
				if(h[mid]<a[i])l=mid+1;
				else r=mid;
			}
			h[l]=a[i];
		}
	}
	printf("%d",t);
	return 0;
}