#include using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<48||ch>57){if(ch=='-')f=-1;ch=getchar();} while(ch>=48&&ch<=57)x=(x<<1)+(x<<3)+(ch&15),ch=getchar(); return x*f; } inline void write(int x) { if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar(x%10+48); return; } constexpr int Mx=1e5+4; mt19937_64 dg(time(0)); int root,tot; struct FHQ_Treap { int l,r,size,v,mkadd,key; FHQ_Treap(){v=l=r=size=0,key=-1,mkadd=0;} FHQ_Treap(int val){l=r=0,v=val,key=dg(),size=1,mkadd=0;} }tr[Mx]; inline int newnode(int val) { int id=++tot; tr[id]=FHQ_Treap(val); return id; } inline void combine(int rt){tr[rt].size=tr[tr[rt].l].size+tr[tr[rt].r].size+1;return;} inline void pushdown_add(int rt,int v) { tr[rt].v+=v; tr[rt].mkadd+=v; return; } inline void pushdown(int rt) { if(!tr[rt].mkadd)return; pushdown_add(tr[rt].l,tr[rt].mkadd); pushdown_add(tr[rt].r,tr[rt].mkadd); tr[rt].mkadd=0; return; } //inline void split_by_size(int rt,int val,int&l,int&r) //{ // if(!rt){l=r=0;return;} // pushdown(rt); // if(tr[tr[rt].l].size