因为实力太拉所以照着 OI wiki 写的，但是 WA 28pts。

个人感觉码风较好。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
const double alpha = 0.75;
struct ScapeGoatTree {
	int cnt, rt;
	int w[N], lc[N], rc[N];
	int wn[N], s[N];
	int sz[N], sd[N];
	int ldr[N];
	void Calc(int k) {
		s[k] = s[lc[k]]+s[rc[k]]+1;
		sz[k] = sz[lc[k]]+sz[rc[k]]+wn[k];
		sd[k] = sd[lc[k]]+sd[rc[k]]+(wn[k]!=0); 
	}
	// Rebuild 
	bool CanRbu(int k) {return wn[k]&&(alpha*s[k]<=(double)max(s[lc[k]], s[rc[k]])||(double)sd[k]<=alpha*s[k]);}
	void Rbu_Flt(int &ldc, int k) {
		if(!k) return ;
		Rbu_Flt(ldc, lc[k]);
		if(wn[k]) ldr[ldc++] = k;
		Rbu_Flt(ldc, rc[k]);
	}
	int Rbu_Bld(int l, int r) {
		int mid = l+r>>1;
		if(l>=r) return 0;
		lc[ldr[mid]] = Rbu_Bld(l, mid);
		rc[ldr[mid]] = Rbu_Bld(mid+1, r);
		Calc(ldr[mid]);
		return ldr[mid]; 
	}
	void Rbu(int &k) {
		int ldc = 0;
		Rbu_Flt(ldc, k);
		k = Rbu_Bld(0, ldc);
	}
	// Rebuild 
	void ins(int& k, int p) {
		if(!k) {
			k = ++cnt;
	    	if(!rt) rt = 1;
	    	w[k] = p;
	   	 	lc[k] = rc[k] = 0;
	  	  	wn[k] = s[k] = sz[k] = sd[k] = 1;
	  	}else {
	  	  	if(w[k]==p) wn[k]++;
	   	 	else if(w[k]<p) ins(rc[k], p);
	   	 	else ins(lc[k], p);
	   	 	Calc(k);
	   	 	if(CanRbu(k)) Rbu(k);
	  	}
	}
	void del(int& k, int p) {
	  	if(!k) return ;
	  	else {
	    	if(w[k]==p)
				if(wn[k]) wn[k]--;
	    	else {
	      		if(w[k]<p) del(rc[k], p);
	      		else del(lc[k], p);
	    	}
	    	Calc(k);
	    	if(CanRbu(k)) Rbu(k);
	  	}
	}
	int UpperBound(int k, int p) {
	  	if(!k) return 1;
	  	else if(w[k]==p&&wn[k]) return sz[lc[k]]+wn[k]+1;
	  	else if(p<w[k]) return UpperBound(lc[k], p);
	  	else return sz[lc[k]]+wn[k]+UpperBound(rc[k], p);
	}
	int LowerBound(int k, int p) {
	  	if(!k) return 0;
	  	else if(w[k]==p&&wn[k]) return sz[lc[k]];
	  	else if(w[k]<p) return sz[lc[k]]+wn[k]+LowerBound(rc[k], p);
	  	else return LowerBound(lc[k], p);
	}
	int At(int k, int p) {
		if(!k) return 0;
		else if(sz[lc[k]]<p&&p<=sz[lc[k]]+wn[k]) return w[k];
		else if(sz[lc[k]]+wn[k]<p) return At(rc[k], p-sz[lc[k]]-wn[k]);
		else return At(lc[k], p);
	}
	inline int Pre(int k, int p) {return At(k, LowerBound(k, p));}
	inline int Nxt(int k, int p) {return At(k, UpperBound(k, p));}
//	inline int Rnk(int x) {return ;}
}sgt;
int main() {
	int n, opt, x;
	cin >> n;
	while(n--) {
		cin >> opt >> x;
		if(opt==1) sgt.ins(sgt.rt, x);
		else if(opt==2) sgt.del(sgt.rt, x);
		else if(opt==3) cout << sgt.LowerBound(sgt.rt, x)+1 << endl;
		else if(opt==4) cout << sgt.At(sgt.rt, x) << endl;
		else if(opt==5) cout << sgt.Pre(sgt.rt, x) << endl;
		else if(opt==6) cout << sgt.Nxt(sgt.rt, x) << endl;
	}
	return 0;
}