#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], f[N];
int n = 0, i = 0;
int find1(int x, int n) { // first <= x
	int l = 1, r = n;
	while (l + 1 < r) {
		int mid = (l + r) >> 1;
		if (a[mid] <= x) {
			r = mid;
		} else {
			l = mid;
		}
	}
	return r;
}
int find2 (int x, int n) { // first >= x
	int l = 1, r = n;
	while (l + 1 < r) {
		int mid = (l + r) >> 1;
		if (a[mid] >= x) {
			r = mid;
		} else {
			l = mid;
		}
	}
	return r;
}
int main() {
    memset(f, 0x3f, sizeof f);
	while (scanf("%d", &a[++n]) != EOF) {
		if (a[n] <= f[i]) f[++i] = a[n];
		else f[find1(a[n], i)] = a[n];
	}
	cout << i << endl;
	i = 0;
	memset(f, 0, sizeof f);
	for (int j = 1; j < n; j++) {
		if (a[j] > f[i]) f[++i] = a[j];
		else f[find2(a[j], i)] = a[j];
	}
	cout << i << endl;
	return 0;
}