#include<bits/stdc++.h>
using namespace std;
int p1[100001], p2[100001],a[100001],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];
	cout<<tot<<endl;
	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];
	cout<<tot;
}