1 #include
     
       2 using namespace std; 3 const int N=510,M=251000,oo=2e9; 4 int n,a[N],f[N],ss,tt; 5 struct Edge{ 6     int from,to,flow,cap; 7     Edge(int _from=0,int _to=0,int _flow=0,int _cap=0):from(_from),to(_to),flow(_flow),cap(_cap){} 8 }; 9 Edge edge[M<<1];10 int edge_tot,spe[10];11 vector
      
       point[N<<1];12 void add_edge(int f,int t,int c){13     edge[edge_tot]=Edge(f,t,0,c);14     point[f].push_back(edge_tot++);15     edge[edge_tot]=Edge(t,f,0,0);16     point[t].push_back(edge_tot++);17     return;18 }19 int level[N<<1];20 bool bfs(){21     memset(level,0,sizeof(level));22     queue
       
        q;23     q.push(ss);24     level[ss]=1;25     int x;26     while(!q.empty()){27         x=q.front();q.pop();28         for(int i=0;i
        
         e.flow&&!level[e.to]){31                 level[e.to]=level[x]+1;32                 q.push(e.to);33             }34         }35     }36     return level[tt];37 }38 int dfs(int k,int aa){39     if(k==tt||!aa) return aa;40     int temp,ans=0;41     for(int i=0;i
         
          e.flow&&level[e.to]==level[k]+1&&(temp=dfs(e.to,min(aa,e.cap-e.flow)))){44             ans+=temp,aa-=temp;45             e.flow+=temp,edge[point[k][i]^1].flow-=temp;46         }47         if(!aa) return ans;48     }49     return ans;50 }51 int dinic(){52     int ans=0;53     while(bfs()) ans+=dfs(ss,oo);54     return ans;55 }56 int main(){57 //  freopen("in.txt","r",stdin);58 //  freopen("out.txt","w",stdout);59     int ans1=0,ans2=0,ans3=0;60     scanf("%d",&n);61     ss=(n<<1)+1,tt=ss+1;62     for(int i=1;i<=n;i++) scanf("%d",&a[i]);63     a[n+1]=oo;64     for(int i=n;i;i--){65         for(int j=i+1;j<=n+1;j++) if(a[i]<=a[j]) f[i]=max(f[j]+1,f[i]);66         ans1=max(ans1,f[i]);67     }68     printf("%d\n",ans1);69     for(int i=1;i<=n;i++){70         if(i==1||i==n) spe[++spe[0]]=edge_tot;71         add_edge(i,i+n,1);72         if(f[i]==ans1){73             if(i==1) spe[++spe[0]]=edge_tot;74             add_edge(ss,i,1);75         }76         if(f[i]==1){77             if(i==n) spe[++spe[0]]=edge_tot;78             add_edge(i+n,tt,1);79         }80     }81     for(int i=1;i<=n;i++)82         for(int j=i+1;j<=n;j++) if(a[j]>=a[i]&&f[j]==f[i]-1)83             add_edge(i+n,j,1);84     ans2=dinic();85     printf("%d\n",ans2);86     for(int i=0;i