#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define maxn 1000000#define INF 2147483647int n,fa[maxn],val[maxn],c[maxn][2],root,tot,siz[maxn],cnt[maxn];void Maintain(int x){    siz[x]=siz[c[x][0]]+siz[c[x][1]]+cnt[x];}void NewNode(int &x,int Fa,int key){    x=++tot;    fa[x]=Fa;    c[x][0]=c[x][1]=0;    val[x]=key;    siz[x]=cnt[x]=1;}void Rotate(int x,bool flag){    int y=fa[x];    c[y][!flag]=c[x][flag];    fa[c[x][flag]]=y;    if(fa[y]){        c[fa[y]][c[fa[y]][1]==y]=x;    }    fa[x]=fa[y];    c[x][flag]=y;    fa[y]=x;    Maintain(y);    Maintain(x);}void Splay(int x,int goal){    if(!x){        return;    }    int y;    while((y=fa[x])!=goal){        if(fa[y]==goal){            Rotate(x,c[y][0]==x);        }        else{            if((c[y][0]==x)==(c[fa[y]][0]==y)){                Rotate(y,c[fa[y]][0]==y);            }            else{                Rotate(x,c[y][0]==x);                y=fa[x];            }            Rotate(x,c[y][0]==x);        }    }    Maintain(x);    if(!goal){        root=x;    }}int Find(int key,int x=root){    while(c[x][val[x]
         
          key&&fa[x]){        x=fa[x];    }    return val[x];}int GetNex(int key){    int x=Find(key);    if(val[x]==key){        Splay(x,0);        return val[Findmin(c[x][1])];    }    while(val[x]