#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false); cin.tie(nullptr)
#define ft first
#define sd second
typedef long long ll;
using namespace std;
const int INF=0x3f3f3f3f;
const int MN=1e5+20;
int a[MN];
int f[MN];
inline void solve(){
	int idx=0,x=0;
	while(cin >> x){
		a[++idx]=x;
	}
	int n=idx;
	int len=0;
	a[0]=INF;
	for(int i=1;i<=n;i++){
		int l=0,r=len;
		while(l<r){
			int mid=r+l+1 >> 1;
			if(f[mid]>=a[i]) l=mid;
			else
				r=mid-1;
		}
		len=max(len,r+1);
		f[r+1]=a[i];
	}
	cout << len << '\n';
	set<int> st;
	st.insert(a[1]);
	for(int i=2;i<=n;i++){
		auto it=lower_bound(st.begin(),st.end(),a[i]);
		if(it!=st.end()){
			st.erase(it);
			st.insert(a[i]);
		}
		else st.insert(a[i]);
	}
	cout << st.size();
	return;
}
int main(){
	FAST;
//	int t;
//	cin >> t;
//	while(t--)
	solve();
	return 0;
}