#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
using namespace std;
inline char gt()
{
    return getchar();
//	static char buf[1 << 21], *p1 = buf, *p2 = buf;
//	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void  read(T &x)
{
	register char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x)
{
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar('\n');
}
typedef long long lxl;
const int N = 1000079;
int a[N];
int c[N];
const int M=50005;
inline int lowbit(int x)
{
	return x & -x;
}
inline void add1(int x, int v)
{
	for(; x <= M; x += lowbit(x))
		c[x] = max(c[x], v);
}
inline void add2(int x, int v)
{
	for(; x; x -= lowbit(x))
		c[x] = max(c[x], v);
}
inline int ask1(int x)
{
	int maxx = 0;
	for(; x; x -= lowbit(x));
	maxx = max(c[x], maxx);
	return maxx;
}
inline int ask2(int x)
{
	int maxx = 0;
	for(; x <= M; x += lowbit(x));
	maxx = max(c[x], maxx);
	return maxx;
}
int main()
{
	int tot = 0;
	while(~scanf("%d", &a[++tot]));
	tot--;
	int ans = 0;
	rep(i, 1, tot)
	{
		int q = ask1(a[i]) + 1;
		ans = max(ans, q);
		add1(a[i] + 1, q);
	}
	memset(c, 0, sizeof c);
	int anss = 0;
	rep(i, 1, tot)
	{
		int q = ask2(a[i]) + 1;
		anss = max(anss, q);
		add2(a[i], q);
	}
	out(anss);
	out(ans);
	return 0;
}