lrx___ @ 2024-08-15 11:28:44
#define ___coding
#ifdef ___coding
#define ___coding1 true
#else
#define ___coding1 false
#endif
#include<cmath>
#include<cassert>
#include<cctype>
#include<climits>
#include<cstdlib>
#include<cstdio>
#include<cstdint>
#include<cstring>
#include<ctime>
#include<limits>
#include<algorithm>
#include<bitset>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<memory>
#include<queue>
#include<stack>
#include<set>
#include<sstream>
#include<string>
#include<utility>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#define UP(i,a,b) for(i=a;i<=(b);++i)
#define DN(i,a,b) for(i=a;i>=(b);--i)
#define up(i,a,b) for(i=a;i<(b);++i)
#define dn(i,a,b) for(i=a;i>(b);--i)
#define pr make_pair
typedef unsigned char unc;
typedef unsigned short uns;
typedef unsigned uni;
typedef unsigned long unl;
typedef long long ll;
typedef unsigned long long ull;
const int BUF_SIZE(1<<14);
bool ___f;
char ___c,___a[45],*___p,___ibuf[BUF_SIZE+1],*___ib(___ibuf),*___ie(___ibuf),___obuf[BUF_SIZE+1],*___ob(___obuf),*___oe(___obuf+BUF_SIZE);
char& gtch(){if(___ib==___ie)___ie=(___ib=___ibuf)+fread(___ibuf,1,BUF_SIZE,stdin);if(___ib==___ie){return *___ibuf=-1;}return *___ib++;}
void ___flush(){fwrite(___obuf,1,___ob-___obuf,stdout);___ob=___obuf;}
void ptch(char c){if(___ob==___oe)___flush();*___ob=c;++___ob;}
typedef __int128 pll;
typedef unsigned __int128 upll;
void rd(pll &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(upll &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void wt(pll r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(upll r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void rd(bool &r){r=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r|=bool(___c^'0');}}
void rd(char &c){for(c=gtch();c==' '||c=='\r'||c=='\n';c=gtch());}
void rd(short &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(short)(___c^'0');}if(___f){r=~(r-1);}}
void rd(int &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(long &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(ll &r){r=0;___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch()){___f=(___c=='-');}for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}if(___f){r=~(r-1);}}
void rd(unc &c){for(c=gtch();c==' '||c=='\r'||c=='\n';c=gtch());}
void rd(uns &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(uns)(___c^'0');}}
void rd(uni &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void rd(unl &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void rd(ull &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch()){r=(r<<3)+(r<<1)+(___c^'0');}}
void rd(char *s){for(*s=gtch();*s==' '||*s=='\r'||*s=='\n';*s=gtch());for(;~*s&&*s!=' '&&*s!='\r'&&*s!='\n';++s,*s=gtch());*s=0;}
void rd(char *s,char n){for(*s=gtch();*s==' '||*s=='\r'||*s=='\n';*s=gtch());for(;~*s&&*s!=n;++s,*s=gtch());*s=0;}
void wt(bool a){ptch('0'+a);}
void wt(char c){ptch(c);}
void wt(short r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(int r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(long r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(ll r){if(!r){ptch('0');return;}if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(unc c){ptch(c);}
void wt(uns r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(uni r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(unl r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(ull r){if(!r){ptch('0');return;}___p=___a;while(r!=0){++___p;*___p=char(r%10)^'0';r/=10;}while(___p!=___a){ptch(*___p);--___p;}}
void wt(char *s){for(;*s;++s){ptch(*s);}}
void wt(const char *s){for(;*s;++s){ptch(*s);}}
template<typename T,typename ...T1>void rd(T &a,T1 &...b){rd(a);rd(b...);}
template<typename T,typename ...T1>void wt(T a,T1 ...b){wt(a);wt(b...);}
template<typename T>void RD(T* a,int n=1){while(n--){rd(*a);++a;}}
ll llabs1(ll a){return a<0?-a:a;}
template<typename T>T ___min(T &a,T &b){return a<b?a:b;}
template<typename T,typename ...T1>T ___min(T &a,T &b,T1 &...c){return ___min(a,b=___min(b,c...));}
template<typename ...T>auto min(T ...a){return ___min(a...);}
template<typename T>T ___max(T &a,T &b){return a>b?a:b;}
template<typename T,typename ...T1>T ___max(T &a,T &b,T1 &...c){return ___max(a,b=___max(b,c...));}
template<typename ...T>auto max(T ...a){return ___max(a...);}
/*
*/
const int N(1005),M(2e6+1e3+5),INF(1e9);
int hd[N],ed[M][3],ee,pre[N],dep[N],gap[N],now[N],a[N],dp[N],n,m,vtx,s,t,ans;
std::queue<int> q;
void add_edge(int u,int v,int w){
ed[++ee][0]=hd[u];
ed[ee][1]=v;
ed[ee][2]=w;
hd[u]=ee;
}
void add(int u,int v,int w){
add_edge(u,v,w);add_edge(v,u,w);
}
void bfs(){
int i,u,v,w;
memcpy(now+1,hd+1,vtx<<2);
memset(dep+1,0,vtx<<2);
memset(gap+1,0,vtx<<2);
dep[t]=1;q.push(t);
while(q.size()){
u=q.front();q.pop();
++gap[dep[u]];
for(i=hd[u];i;i=ed[i][0]){
v=ed[i][1];w=ed[i^1][2];
if(w>0&&dep[v]==0){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
}
int isap(){
int i,u,v,w,flow(0),res;
bfs();
u=s;
while(dep[s]<=vtx){
if(u==t){
res=INF;v=t;
while(v!=s){
res=min(res,ed[pre[v]][2]);
v=ed[pre[v]^1][1];
}
flow+=res;v=t;
while(v!=s){
ed[pre[v]][2]-=res;
ed[pre[v]^1][2]+=res;
v=ed[pre[v]^1][1];
}
u=s;
}
for(i=now[u];i;i=ed[i][0]){
v=ed[i][1];w=ed[i][2];
if(w>0&&dep[v]==dep[u]-1){
now[u]=pre[v]=i;
u=v;
goto lb1;
}
}
if(!--gap[dep[u]]){
break;
}
dep[u]=INF;
for(i=now[u]=hd[u];i;i=ed[i][0]){
v=ed[i][1];w=ed[i][2];
if(w>0){
dep[u]=min(dep[u],dep[v]+1);
}
}
if(dep[u]<INF){
++gap[dep[u]];
}
if(u!=s){
u=ed[pre[u]^1][1];
}
lb1:;
}
return flow;
}
void clear_graph(){
memset(hd+1,0,vtx<<2);ee=1;
}
void ___main(){
int i,j;
rd(n);
RD(a+1,n);
ans=0;
DN(i,n,1){
UP(j,i+1,n){
if(a[j]>=a[i]){
dp[i]=max(dp[i],dp[j]);
}
}
++dp[i];
ans=max(ans,dp[i]);
}
wt(ans,'\n');
if(ans==1){
wt(n,'\n',n,'\n');
return;
}
vtx=n<<1;s=++vtx;t=++vtx;
clear_graph();
UP(i,1,n){
if(dp[i]==ans){
add(s,i,1);
}else if(dp[i]==1){
add(i+n,t,1);
}
add(i,i+n,1);
UP(j,i+1,n){
if(dp[j]==dp[i]-1&&a[j]>=a[i]){
add(i+n,j,1);
}
}
}
wt(isap(),'\n');
clear_graph();
UP(i,1,n){
if(dp[i]==ans){
add(s,i,i==1||i==n?INF:1);
}else if(dp[i]==1){
add(i+n,t,i==1||i==n?INF:1);
}
add(i,i+n,i==1||i==n?INF:1);
UP(j,i+1,n){
if(dp[j]==dp[i]-1&&a[j]>=a[i]){
add(i+n,j,1);
}
}
}
wt(isap(),'\n');
}
int main(){if(___coding1)freopen("in.txt","r",stdin);___main();___flush();if(___coding1){freopen("CON","r",stdin);system("pause");}return 0;}
by GX0303 @ 2024-10-07 10:20:35
6