#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, s[100001], f[100001];
signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> s[i];
	f[1] = 1;
	int maxn = 1, mn = 1;
	for (int i = 2; i <= n; i++) {
		
//			if (s[j] >= s[i]) f[i] = max(f[j] + 1, f[i]);
//			if (f[i] >= maxn) maxn = f[i];
			int m = 0;
			for (int j = 1; j < i; j++) {
				if (f[j] > m && s[i] <= s[j])  m = f[j];
			}
			f[i] = m + 1;
			if (f[i] > maxn)   maxn = f[i];
		
	}
	fill(f + 1, f + 1 + n, 0);
	f[1] = 1;
	for (int i = 2; i <= n; i++) {
			int m = 0;
//			if (s[j] < s[i]) f[i] = max(f[j] + 1, f[i]);
//			if (f[i] >= mn) mn = f[i];
			for (int j = 1; j < i; j++) {
				if (f[j] > m && s[i] > s[j])  m = f[j];
			}
			f[i] = m + 1;
			if (f[i] > mn)   mn = f[i];
		
	}
	cout << maxn << '\n' << mn;
}