#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef long long LL;
struct edge
{
	LL x,cap,rev;
};
vector<edge> e[N];
int n,m,s,t;
int d[N],it[N];
void add(int a,int b,LL c)
{
	e[a].push_back({b,c,(LL)e[b].size()});
	e[b].push_back({a,0,(LL)e[a].size() - 1});
}
void bfs()
{
	memset(d,-1,sizeof d);
	queue<int> q;
	d[s] = 0;
	q.push(s);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(auto t : e[u])
			if(t.cap > 0 && d[t.x] < 0) d[t.x] = d[u] + 1,q.push(t.x);
	}
}
LL dfs(int u,LL f)
{
	if(u == t) return f;
	for(int &i = it[u]; i < e[u].size(); i ++)
	{
		edge &t = e[u][i]; 
		if(d[u] < d[t.x] && t.cap > 0)
		{
			LL d = dfs(t.x,min(f,t.cap));
			if(d > 0)
			{
				t.cap -= d;
				e[t.x][t.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}
LL dinic() 
{
	LL flow = 0;
	while(1)
	{
		bfs();
		if(d[t] < 0) break;
		memset(it,0,sizeof it);
		LL d = dfs(s,1e18);
		while(d > 0)
		{
			flow += d;
			d = dfs(s,1e18);
		}
	}
	return flow;
}
const int M = 510;
int a[M],f[M],cnt;
int lis()
{
	for(int i = 1; i <= n; i ++) f[i] = 1;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j < i; j ++)
			if(a[j] <= a[i]) f[i] = max(f[i],f[j] + 1);
	int res = 0;
	for(int i = 1; i <= n; i ++) res = max(res,f[i]);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	s = 0,t = 2 * n + 1;
	for(int i = 1; i <= n; i ++) cin>>a[i],add(i,i + n,1);
	int res = lis();
	cout<<res<<endl;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j < i; j ++)
			if(a[j] <= a[i] && f[i] == f[j] + 1) add(j + n,i,1);
	for(int i = 1; i <= n; i ++)
		if(f[i] == res) add(i + n,t,1);
	for(int i = 1; i <= n; i ++) 
		if(f[i] == 1) add(s,i,1);
	LL flow = dinic();
	cout<<flow<<endl;
	for(int i = s; i <= t; i ++) e[i].clear();
	for(int i = 1; i <= n; i ++)
		if(i == 1 || i == n) add(i,i + n,1e9);
		else add(i,i + n,1);
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j < i; j ++)
			if(a[j] <= a[i] && f[i] == f[j] + 1) add(j + n,i,1);
	for(int i = 1; i <= n; i ++)
		if(f[i] == res && (i == 1 || i != n)) add(i + n,t,1);
		else if(f[i] == res) add(i + n,t,1e9);
	for(int i = 1; i <= n; i ++)
		if(f[i] == 1 && (i == n || i != 1)) add(s,i,1);
		else if(f[i] == 1) add(s,i,1e9);
	flow = dinic();
	cout<<flow<<endl;
	return 0;
}