#include #include #include #include #include #include using namespace std; #define MAXN 150001 #define Inf (1<<6)+1 struct BTNode { int item,lc,rc,up; int cnt; BTNode(){cnt=1;} }BT[MAXN]; int root,T; int Ptr[MAXN*3],top,pt; int N; int Ans; int Num[MAXN],Res[MAXN]; void Init() { root=0;top=-1;pt=1; memset(BT,0,sizeof(BT)); } void Rotate(int i) { if(BT[i].up==0)return; int upper=BT[i].up; if(BT[upper].lc==i) { BT[upper].lc=BT[i].rc; BT[BT[i].rc].up=upper; BT[i].rc=upper; } else { BT[upper].rc=BT[i].lc; BT[BT[i].lc].up=upper; BT[i].lc=upper; } BT[i].up=BT[upper].up; BT[upper].up=i; if(BT[i].up==0){root=i;} else { if(BT[BT[i].up].lc==upper)BT[BT[i].up].lc=i; else {BT[BT[i].up].rc=i;} } BT[upper].cnt=BT[i].cnt=1; if(BT[upper].lc)BT[upper].cnt+=BT[BT[upper].lc].cnt; if(BT[upper].rc)BT[upper].cnt+=BT[BT[upper].rc].cnt; if(BT[i].lc)BT[i].cnt+=BT[BT[i].lc].cnt; if(BT[i].rc)BT[i].cnt+=BT[BT[i].rc].cnt; } void Splay(int i) { while(root!=i) { Rotate(i); } } int Find(int x,int &modif) { int id=root,upper=0,val,dir=0; modif=0; while(id!=0) { val=BT[id].item; if(val==x)return id; upper=id; if(x>=val){id=BT[id].rc;dir=1;} else {id=BT[id].lc;dir=-1;} } modif=dir; return upper; } void Insert(int x) { int id=root,upper=0,val,dir=0; while(id!=0) { val=BT[id].item; upper=id; if(x>=val){id=BT[id].rc;dir=1;} else {id=BT[id].lc;dir=-1;} } if(top==-1) { Ptr[pt]=top; top=pt++; } id=top; top=Ptr[top]; BT[id].up=upper;BT[id].item=x; BT[id].lc=BT[id].rc=0; if(upper>0) { if(dir==1)BT[upper].rc=id; else {BT[upper].lc=id;} } else { root=id; } Splay(id); } int Maxelem() { int id=root; if(id==0)return 0; while(BT[id].rc!=0) { id=BT[id].rc; } return id; } int Minelem() { int id=root; if(id==0)return 0; while(BT[id].lc!=0) { id=BT[id].lc; } return id; } int Pro(int x) { int u=0,ret; int id=Find(x,u); if(u!=0)return 0; Splay(id); BT[BT[id].lc].up=0; root=BT[id].lc; ret=Maxelem(); root=id; BT[BT[id].lc].up=id; return ret; } int Succ(int x) { int u=0,ret; int id=Find(x,u); if(u!=0)return 0; Splay(id); BT[BT[id].rc].up=0; root=BT[id].rc; ret=Minelem(); root=id; BT[BT[id].rc].up=id; return ret; } void Delete(int x) { int id=root,upper,modif=0,Mid,uMid; /*id=Find(x,modif); if(modif!=0 || root==0)return;*/ id=x; Splay(id); upper=id; id=BT[id].lc; if(id>0) { BT[id].up=0; root=id; Mid=Maxelem(); /*Ptr[Mid]=top; top=Mid; uMid=BT[Mid].up; if(uMid>0) { if(BT[uMid].lc==Mid)BT[uMid].lc=BT[Mid].lc; else {BT[uMid].rc=BT[Mid].lc;} if(BT[Mid].lc>0)BT[BT[Mid].lc].up=uMid; BT[id].up=upper; } else { id=BT[Mid].lc; if(BT[Mid].lc>0){BT[id].up=upper;} }*/ Splay(Mid); BT[Mid].rc=BT[upper].rc; BT[BT[upper].rc].up=Mid; if(BT[root].rc)BT[root].cnt+=BT[BT[root].rc].cnt; } else { BT[BT[upper].rc].up=0; root=BT[upper].rc; } Ptr[upper]=top; top=upper; } int Searchkth(int tid,int k) { if(!tid || k>BT[tid].cnt)return -1; int lcc=0; if(BT[tid].lc)lcc=BT[BT[tid].lc].cnt; if(k==lcc+1)return tid; if(k<=lcc)return Searchkth(BT[tid].lc,k); else {return Searchkth(BT[tid].rc,k-lcc-1);} } int main() { scanf("%d",&T); while(T--) { scanf("%d",&N); Init(); for(int i=1;i<=N;i++){Insert(i);scanf("%d",&Num[i]);} for(int i=N;i>=1;i--) { Num[i]-=Num[i-1]; int K=i-Num[i]; //cout<<"K="<