#include<bits/stdc++.h>
using namespace std;
int a[100005],ans;
vector<int> g,f;
int main()
{
	while(cin>>a[++a[0]]);
	--a[0];
	for(int i=1;i<=a[0];++i)
	{
		if(f.empty()||f[0]>a[i])
		{
			f.insert(f.begin(),1,a[i]);
		}else
		{
			int id=upper_bound(f.begin(),f.end(),a[i])-f.begin();
			//cout<<id<<"  ";
			f[id-1]=a[i];
		}
		/*for(vector<int>::iterator it=f.begin();it!=f.end();++it)
		  cout<<*it<<' ';
		cout<<'\n';*/
	}
	cout<<f.size()<<'\n';
	for(int i=1;i<=a[0];++i)
	{
		if(g.empty()||g[g.size()-1]<a[i])
		{
			g.insert(g.end(),1,a[i]);
			//cout<<-1<<"  ";
		}else
		{
			int id=lower_bound(g.begin(),g.end(),a[i])-g.begin();
			//cout<<id<<"  ";
			g[id]=a[i];
		}
		/*for(vector<int>::iterator it=g.begin();it!=g.end();++it)
		  cout<<*it<<' ';
		cout<<'\n';*/
	}
	cout<<g.size();
 }