#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int x,int y)
{
	return x > y;
}
int a[1000100];
int g[1000100];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	int sz = 0;
	for (int i = 1; i <= n; i++) 
	{
		int pos = upper_bound(g+1,g+sz+1,a[i],cmp) - g;
		g[pos] = a[i];
		sz = max(sz,pos);
	}
	cout << sz << endl;
	sz = 0;
	for (int i = 1; i <= n; i++) 
	{
		int pos = lower_bound(g+1,g+sz+1,a[i]) - g;
		g[pos] = a[i];
		sz = max(sz,pos);
	}
	cout << sz;
	return 0;
}