#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stdlib.h>
using namespace std;
int st[100001],a[100001],g[100001];
int top,n,ans;
void input(int k){
	if(st[top]>=k){
		st[++top]=k;
		return;
	}
	int l=1,r=top;
	while(l<r){
		int mid=(l+r)>>1;
		if(st[mid]<k)
			l=mid+1;
		else
			r=mid;
	}
	st[l]=k;
}
int main(){
	while(cin>>a[++n])
		input(a[n]);
	cout<<top<<endl;
	for(int i=1;i<=n;i++){
		int k=0;
		while(k<=ans&&g[k]<a[i])k++;
		if(k>ans) g[++ans]=a[i];
		else	g[k]=a[i];
	}	
	cout<<ans;
	return 0;
}