#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 RangeSet{ set> st; T TINF; RangeSet(){ TINF=numeric_limits::max()/2; st.emplace(TINF,TINF); st.emplace(-TINF,-TINF); } // [l,r] covered? bool contains(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); return ite->first<=l and r<=ite->second; } bool contains(T x){ return contains(x,x); } // covered by // [l, r]がカバーされているなら,その区間を返す // されていないなら-TINFを返す pair covered_by(T l,T r){ auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second) return *ite; return make_pair(-TINF,-TINF); } // [x, x]がカバーされているなら,その区間を返す pair covered_by(T x){ return covered_by(x,x); } // insert[l,r], 増加量を返す T insert(T l,T r){ auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second) return T(0); T sum_erased=T(0); if(ite->first<=l and l<=ite->second+1){ l=ite->first; sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); }else ite=next(ite); while(r>ite->second){ sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); } if(ite->first-1<=r and r<=ite->second){ sum_erased+=ite->second-ite->first+1; r=ite->second; st.erase(ite); } st.emplace(l,r); return r-l+1-sum_erased; } T insert(T x){ return insert(x,x); } // erase [l,r], 減少量を返す T erase(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second){ // 完全に1つの区間に包含されている if(ite->firstfirst,l-1); if(rsecond) st.emplace(r+1,ite->second); st.erase(ite); return r-l+1; } T ret=T(0); if(ite->first<=l and l<=ite->second){ ret+=ite->second-l+1;// 消えた if(ite->firstfirst,l-1); ite=st.erase(ite);// 次へ }else ite=next(ite); while(ite->second<=r){ ret+=ite->second-ite->first+1; ite=st.erase(ite); } // 右端が区間の間にあるか if(ite->first<=r and r<=ite->second){ ret+=r-ite->first+1; if(rsecond) st.emplace(r+1,ite->second); st.erase(ite); } return ret; } T erase(T x){ return erase(x,x); } // number of range int size(){ return (int)st.size()-2; } // mex [x,~) int mex(T x=0){ auto ite=prev(st.lower_bound({x+1,x+1})); if(ite->first<=x and x<=ite->second) return ite->second+1; else return x; } void output(){ cout<<"RangeSet : "; for(auto &p:st){ if(p.first==-TINF or p.second==TINF) continue; cout<<"["<>d>>q; RangeSet st; ll res=0; while(q--){ ll l,r;cin>>l>>r; st.insert(l,r); auto p=st.covered_by(l); chmax(res,p.second-p.first+1); cout<