/*
14
67 66 65 64 63 62 62 60 59 58 57 56 55 54
*/
#include <cstdio>
#include <algorithm>

using namespace std;

int size[114514], a[114514], b[114514], nums[114514];
int len = 0, maxlen = -1, pos = 0;

int max(int a, int b) {
	return a > b ? a : b;
}

int main() {
	while (~scanf("%d", &nums[++ len]));
	-- len;
	int x = 1;
	b[1] = nums[1];
	for (int i = 2; i <= len; i ++) {
		if (nums[i] < b[x]) {
			b[++ x] = nums[i];
		} else {
			int y = lower_bound(b + 1, b + x + 1, nums[i], greater < int > ()) - b;
			b[y] = nums[i];
		}
	}
	printf("%d\n", x);
	x = 1;
	a[1] = nums[1];
	for (int i = 2; i <= len; i ++) {
		if (nums[i] >= a[x]) {
			a[++ x] = nums[i];
		} else {
			int y = upper_bound(a + 1, a + x + 1, nums[i], less < int > ()) - a;
			a[y] = nums[i];
		}
	}
	printf("%d", x);
	return 0;
}