#include #include #include using namespace std; #define ll long long #define N 71000 struct node { int l,r,v,size,rnd; }rt[N]; int size,root; void updata(int x) { rt[x].size=rt[rt[x].l].size+rt[rt[x].r].size+1; } void lturn(int &x) { int y=rt[x].r; rt[x].r=rt[y].l; rt[y].l=x; updata(x); updata(y); x=y; } void rturn(int &x) { int y=rt[x].l; rt[x].l=rt[y].r; rt[y].r=x; updata(x); updata(y); x=y; } void insert(int &x,int val) { if(x==0) { size++; x=size; rt[x].rnd=rand(); rt[x].size=1; rt[x].v=val; return; } rt[x].size++; if(val>rt[x].v) { insert(rt[x].r,val); if(rt[rt[x].r].rndrt[rt[x].r].rnd) lturn(x),del(x,val); else rturn(x),del(x,val); } else { rt[x].size--; if(val>rt[x].v) del(rt[x].r,val); else del(rt[x].l,val); } } int rank1(int x,int num) { if(rt[rt[x].l].size>=num) return rank1(rt[x].l,num); else if(rt[rt[x].l].size+1=1;i--) { int k=rank1(root,i-(a[i]-a[i-1]+1)+1); ans[i]=k; del(root,k); } for(int i=1;i