设\(f[i]\)为以\(i\)结尾的最长上升子序列。可以考虑建这样一张图，对于所有的\(i<j,f[j]=f[i+1]\)连边\((i,j)\)，\(f[i]=1\)的话连边\((S,i)\)，\(f[i]=max(f[j])\)的话连边\((j,T)\)，然后就是删去若干个点使\(S,T\)不连通并且代价最小，那么拆点最小割就行了

然后是字典序的问题。我们把所有的点按\(c\)排个序然后看看这个点也就是新图中的这条边是否可以在最小割里。只要判断一下残量网络中是否存在\(u\)到\(u+n\)的路径就是了

然后删去这条边之后要重新算最大流，如果直接计算会T，这样的话我们可以退流，就是从\(T\)到\(u+n\)跑一次最大流再从\(u\)到\(S\)跑一次最大流就可以消除这条边的影响

//minamoto#include
    
     #define R register#define inf 0x3f3f3f3f#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=1e4+5,M=1e6+5;struct eg{int v,nx,w;}e[M];int head[N],tot=1;inline void add(R int u,R int v,R int w){    e[++tot]={v,head[u],w},head[u]=tot;    e[++tot]={u,head[v],0},head[v]=tot;}struct node{    int c,id;    inline bool operator <(const node &b)const{return c