#include using namespace std; using Int = long long; template struct RBST{ Int xor128(){ static Int x = 123456789; static Int y = 362436069; static Int z = 521288629; static Int w = 88675123; Int t; t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } using F = function; using G = function; using H = function; using P = function; F f; G g; H h; P p; T ti; E ei; struct Node{ Node *l,*r; size_t cnt; T val,dat; E laz; Node():cnt(0){l=r=nullptr;} Node(T val,E laz): cnt(1),val(val),dat(val),laz(laz){l=r=nullptr;} }; const size_t LIM = 2e6; vector pool; size_t ptr; RBST(F f,G g,H h,P p,T ti,E ei): f(f),g(g),h(h),p(p),ti(ti),ei(ei),pool(LIM),ptr(0){} Node* build(size_t l,size_t r,vector &v){ if(l+1==r) return create(v[l]); size_t m=(l+r)>>1; return merge(build(l,m,v),build(m,r,v)); } Node* build(vector &v){ return build(0,v.size(),v); } inline Node* create(){ return &pool[ptr++]; } inline Node* create(T v){ return &(pool[ptr++]=Node(v,ei)); } inline size_t count(const Node* a){ if(a==nullptr) return 0; return a->cnt; } inline Node* insert(Node* a,size_t pos,T v){ Node* b=create(v); auto s=split(a,pos); return a=merge(merge(s.first,b),s.second); } inline Node* erase(Node* a,size_t pos){ auto s=split(a,pos); auto t=split(s.second,1); return merge(s.first,t.second); } inline T query(const Node *a){ if(a==nullptr) return ti; return a->dat; } Node* eval(Node* a){ if(a->laz!=ei){ a->val=g(a->val,p(a->laz,1)); if(a->l!=nullptr){ a->l->laz=h(a->l->laz,a->laz); a->l->dat=g(a->l->dat,p(a->laz,count(a->l))); } if(a->r!=nullptr){ a->r->laz=h(a->r->laz,a->laz); a->r->dat=g(a->r->dat,p(a->laz,count(a->r))); } a->laz=ei; } return update(a); } inline Node* update(Node* a){ if(a==nullptr) return a; a->cnt=count(a->l)+count(a->r)+1; a->dat=f(a->val,f(query(a->l),query(a->r))); return a; } inline T query(Node *&a,size_t l,size_t r){ auto s=split(a,l); auto t=split(s.second,r-l); auto u=t.first; T res=query(u); a=merge(s.first,merge(t.first,t.second)); return res; } inline void update(Node *&a,size_t l,size_t r,E v){ auto s=split(a,l); auto t=split(s.second,r-l); auto u=t.first; u->laz=h(u->laz,v); a=merge(merge(s.first,eval(u)),t.second); } inline T get(Node *&a,size_t p){ auto s=split(a,p); auto t=split(s.second,1); T res=t.first->val; a=merge(s.first,merge(t.first,t.second)); return res; } void dump(Node* a,typename vector::iterator it){ if(!count(a)) return; a=eval(a); dump(a->l,it); *(it+count(a->l))=a->val; dump(a->r,it+count(a->l)+1); } vector dump(Node* a){ vector v(count(a)); dump(a,v.begin()); return v; } Node* merge(Node* a,Node* b){ if(a==nullptr) return b; if(b==nullptr) return a; if(xor128()%(count(a)+count(b))r=merge(a->r,b); return update(a); } b=eval(b); b->l=merge(a,b->l); return update(b); } pair split(Node* a,size_t k){ if(a==nullptr) return make_pair(a,a); a=eval(a); if(k<=count(a->l)){ auto s=split(a->l,k); a->l=s.second; return make_pair(s.first,update(a)); } auto s=split(a->r,k-(count(a->l)+1)); a->r=s.first; return make_pair(update(a),s.second); } }; struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; //INSERT ABOVE HERE signed main(){ RBST::F f=[](Int a,Int b){return max(a,b);}; RBST::G g=[](Int a,Int b){return a+b;}; RBST::P p=[](Int a,size_t b){++b;return a;}; RBST rbst(f,g,g,p,-1,0); using Node = RBST::Node; Int sz=1e5+100; vector v(sz,0); Node* r=rbst.build(v); Int n; cin>>n; for(Int i=0;i>a>>b; r=rbst.erase(r,b); Int k=rbst.query(r,a-1,a); r=rbst.insert(r,a-1,k); rbst.update(r,a,b+1,1); k=rbst.query(r,b,b+1)-1; Int c=b+1,d=sz; while(c+1>1; if(rbst.query(r,b+1,m)>k) d=m; else c=m; } if(b+1