#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10,M = 1e6 + 10,inf = 1e9;
int n,m,head[N],x,y,tot = 1,now[N];
int s,t,flag,vis[N];
int d[N],a[N],k,f[N];
int ans1 = 0,ans2 = 0;
queue<int>q;
struct node{
	int next,to,w;
}edge[M];
void add(int x,int y,int w){
//	if(w != 0) cout<<x<<' '<<y<<' '<<w<<endl;
	++tot;
	edge[tot].next = head[x];
	edge[tot].to = y;
	edge[tot].w = w;
	head[x] = tot;
}
void input(){
	cin>>n;
	s = 0,t = 2 * n + 1;
	for(int i = 1;i <= n; ++i){
		add(i,i + n,1);
		add(i + n,i,0);
	}
	for(int i = 1;i <= n; ++i){
		cin>>a[i];
		f[i] = 1;
		for(int j = 1;j <= i - 1; ++j){
			if(a[j] <= a[i] && f[i] <= f[j] + 1){
				f[i] = f[j] + 1;
				add(j + n,i,1);
				add(i,j + n,0);
			}	
		}
		ans1 = max(ans1,f[i]);
	}
	for(int i = 1;i <= n; ++i){
		if(f[i] == 1) add(s,i,1),add(i,s,0);
		if(f[i] == ans1) add(i + n,t,1),add(t,i + n,0);
	} 
}
bool bfs(){
	for(int i = 0;i <= t; ++i) d[i] = inf;
	for(int i = 0;i <= t; ++i) vis[i] = 0;
	q.push(s);
	vis[s] = 1;d[s] = 1;now[s] = head[s];
	while(!q.empty()){
		x = q.front();
		q.pop();
		for(int i = head[x];i;i = edge[i].next){
			int y = edge[i].to;
			if(edge[i].w > 0 && d[y] == inf){
				d[y] = d[x] + 1;
				now[y] = head[y];
				if(!vis[y]) q.push(y); 
			}
		}
	}
	if(d[t] == inf) return false;
	return true;
}
int dfs(int x,int ent){//流入 
	if(x == t) return ent;
	int res = ent,ned = 0;
	for(int i = now[x];i && res;i = edge[i].next){
		now[x] = i;
		int y = edge[i].to;
		if(edge[i].w <= 0 || d[y] != d[x] + 1) continue;
		int k = dfs(y,min(res,edge[i].w));
		if(k == 0) d[y] = inf;
		res -= k;
		ned += k;
		edge[i].w -= k;
		edge[i ^ 1].w += k;
	}
	return ned;
}
void op(){
	while(bfs()){
//		cout<<d[t];
		int k = dfs(s,inf);
		ans2 += k;
	}
}
void op2(){
	ans2 = 0;
	for(int i = 2;i <= tot;i += 2){
		edge[i].w = 1;
		edge[i + 1].w = 0;
	}
	add(s,1,inf);
	add(1,s,0);
	add(1,1 + n,inf);
	add(1 + n,1,0);
	add(n,2 * n,inf);
	add(2 * n,n,0);
	if(f[n] == ans1){
		add(2 * n,t,inf);
		add(t,2 * n,0);
	}
	op();
	
}
int main(){
	cin.tie(0)->sync_with_stdio(false); 
	input();
	if(ans1 == 1){
		cout<<1<<'\n'<<n<<'\n'<<n;
		return 0;
	}
	op();
	cout<<ans1<<'\n'<<ans2<<'\n';
	op2();
	cout<<ans2;
	return 0;
}