#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #define N 2000005 using namespace std; const int inf=1000000007; int n,m,S,T,tmp1,tmp2,tot; int idx,head[N],cur[N],q[N],ans1[N],ans2[N]; int e[N],ne[N],w[N]; bool b[N]; int r[N],c[N]; int ans; bool vis[N]; int to[N]; int dp[N]; int a[N]; inline void add(int u,int v,int f) { e[idx]=v; w[idx]=f; ne[idx]=head[u]; head[u]=idx++; } inline bool bfs() { int f=0,t=0; memset(cur,-1,sizeof(cur)); q[t++]=0; cur[0]=0; while(f<t) { int now=q[f++]; for(int i=head[now]; ~i; i=ne[i]) { int v=e[i]; if(cur[v]==-1&&w[i]) { cur[v]=cur[now]+1; q[t++]=v; } } } if(cur[T]!=-1) return 1; return 0; } inline int dfs(int x,int f) { if(x==T) return f; int w1,used=0; for(int i=head[x]; ~i; i=ne[i]) { int v=e[i]; if(cur[v]==cur[x]+1&&w[i]) { w1=dfs(v,min(f-used,w[i])); w[i]-=w1; w[i^1]+=w1; used+=w1; if(used==f) return f; } } if(!used) cur[x]=-1; return used; } void dinic() { while(bfs()) ans+=dfs(0,0x3f3f3f3f); } int main() { memset(head,-1,sizeof head); cin>>n; S=0,T=2*n+1; for(int i=1; i<=n; i++) cin>>a[i],dp[i]=1; for(int i=1; i<=n; i++) for(int j=1; j<i; j++) if(a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1); int len=1; for(int i=1; i<=n; i++) len=max(len,dp[i]); if(len==1)//要加特判 { cout<<len<<endl<<n<<endl<<n<<endl; return 0; } cout<<len<<endl; for(int i=1; i<=n; i++) if(dp[i]==1) add(S,i,1),add(i,S,0); for(int i=1; i<=n; i++) if(dp[i]==len) add(i+n,T,1),add(T,i+n,0); for(int i=1; i<=n; i++) add(i,i+n,1),add(n+i,i,0); for(int i=1; i<=n; i++) for(int j=1; j<i; j++) if(a[j]<=a[i]&&dp[j]+1==dp[i]) add(j+n,i,1),add(i,j+n,0); dinic(); cout<<ans<<endl; add(1,1+n,inf); add(1+n,1,0); add(S,1,inf); add(1,S,0); if(dp[n]==len) add(n,n*2,inf),add(n*2,n,0),add(n*2,T,inf),add(T,n*2,0); dinic(); cout<<ans<<endl; return 0; }