#include using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } template struct BinaryTrieMonoid{ private: struct Node{ Node *nxt[2]; Monoid val; Node(Monoid val):nxt{nullptr,nullptr},val(val){} }; Node *root; using F=function; F f; const Monoid e; Monoid query(BitType a,BitType b,Node *cur,BitType l,BitType r,int dep,BitType xor_val){ if(a<=l and r<=b) return (cur?cur->val:e); if(dep<0 or b<=l or r<=a or !cur) return e; bool x0=(xor_val>>dep)&1; Monoid L=query(a,b,cur->nxt[x0],l,(l+r)/2,dep-1,xor_val); Monoid R=query(a,b,cur->nxt[x0^1],(l+r)/2,r,dep-1,xor_val); return f(L,R); } void update(Node *cur,Monoid x,BitType bit,int dep){ if(dep==-1){ cur->val=x; return ; } bool go_to=(bit>>dep)&1; if(!cur->nxt[go_to]) cur->nxt[go_to]=new Node(e); update(cur->nxt[go_to],x,bit,dep-1); cur->val=f(cur->nxt[0]?cur->nxt[0]->val:e,cur->nxt[1]?cur->nxt[1]->val:e); return ; } public: BinaryTrieMonoid(F f,const Monoid &e):root(new Node(e)),f(f),e(e){} // fold [l,r) // xor_valを指定したとき,可換じゃない演算だと壊れると思います.多分 Monoid query(BitType l,BitType r,BitType xor_val=0){ return query(l,r,root,0,BitType(1)< seg([](ll a,ll b){return a+b;},0ll); ll p=0; auto query=[&](ll t){ return seg.query(t-p+geta,geta*4ll); }; auto update=[&](ll t,ll add){ seg.update(t+geta-p,seg[t+geta-p]+add); }; vector memo; int q;cin>>q; while(q--){ int t;ll x;cin>>t>>x; if(t==1){ x-=p; update(x,1); }else if(t==2){ x--; update(memo[x],-1); }else{ p+=x; } memo.push_back(x); ll lw=0,hi=INF,ans=0; while(lw<=hi){ ll mid=(lw+hi)/2; if(query(mid)>=mid) ans=mid,lw=mid+1; else hi=mid-1; } cout<