#include<bits/stdc++.h>
using namespace std;
int p1[100001],p2[100001];
int a[100001];
int n,tot=0;
int work1(int x){
	int l=0,r=tot,ans=1;
	while(l<=r){
		int mid=l+r>>1;
		if(a[mid]<x){
			r=mid-1;
			ans=mid;
		}
		else{
			l=mid+1;
			ans=mid+1;
		}
	}
	return ans;
}
int work(int x){
	int l=0,r=tot,ans=1;
	while(l<=r){
		int mid=l+r>>1;
		if(a[mid]>=x){
			r=mid-1;
			ans=mid;
		}
		else{
			l=mid+1;
			ans=mid+1;
		}
	}
	return ans;
}
int main(){
	int n=0;
	while(cin>>p1[++n]);
	for(int i=1;i<=n;i++){
		if(p1[i]<a[tot]){
			a[++tot]=p1[i];
		}
		else{
			a[work1(p1[i])]=p1[i];
		}
	}
	printf("%d\n",tot);
	for(int i=0;i<=tot;i++){
		a[i]=0;
	}
	tot=0;
	for(int i=1;i<=n;i++){
		if(p1[i]>=a[tot]){
			a[++tot]=p1[i];
		}
		else{
			a[work(p1[i])]=p1[i];
		}
	}
	printf("%d",tot);
	return 0;
}