#include using namespace std; using Int = long long; const char newl = '\n'; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a void drop(const T &x){cout< vector read(size_t n){ vector ts(n); for(size_t i=0;i>ts[i]; return ts; } template struct SegmentTree{ using F = function; using G = function; using H = function; Int n,height; F f; G g; H h; T ti; E ei; vector dat; vector laz; SegmentTree(F f,G g,H h,T ti,E ei): f(f),g(g),h(h),ti(ti),ei(ei){} void init(Int n_){ n=1;height=0; while(n &v){ Int n_=v.size(); init(n_); for(Int i=0;i>i); } inline void recalc(Int k){ while(k>>=1) dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1)); } void update(Int a,Int b,E x){ if(a>=b) return; thrust(a+=n); thrust(b+=n-1); for(Int l=a,r=b+1;l>=1,r>>=1){ if(l&1) laz[l]=h(laz[l],x),l++; if(r&1) --r,laz[r]=h(laz[r],x); } recalc(a); recalc(b); } void set_val(Int a,T x){ thrust(a+=n); dat[a]=x;laz[a]=ei; recalc(a); } T query(Int a,Int b){ if(a>=b) return ti; thrust(a+=n); thrust(b+=n-1); T vl=ti,vr=ti; for(Int l=a,r=b+1;l>=1,r>>=1) { if(l&1) vl=f(vl,reflect(l++)); if(r&1) vr=f(reflect(--r),vr); } return f(vl,vr); } template Int find(Int st,C &check,T &acc,Int k,Int l,Int r){ if(l+1==r){ acc=f(acc,reflect(k)); return check(acc)?k-n:-1; } propagate(k); Int m=(l+r)>>1; if(m<=st) return find(st,check,acc,(k<<1)|1,m,r); if(st<=l and !check(f(acc,dat[k]))){ acc=f(acc,dat[k]); return -1; } Int vl=find(st,check,acc,(k<<1)|0,l,m); if(~vl) return vl; return find(st,check,acc,(k<<1)|1,m,r); } template Int find(Int st,C &check){ T acc=ti; return find(st,check,acc,1,0,n); } }; //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); Int n; cin>>n; auto as=read(n); if(n==1){ Int q; cin>>q; for(Int i=0;i>p>>x; cout< seg(f,g,g,-INF,0); seg.build(vector(n-1,0)); for(Int i=0;i ms(as.begin(),as.end()); Int q; cin>>q; for(Int i=0;i>p>>x; p--; Int &a=as[p]; seg.update(idx(a),n-1,-1); num-=floor(n-2-a,n-1); ms.erase(ms.find(a)); a=x; seg.update(idx(a),n-1,+1); num+=floor(n-2-a,n-1); ms.emplace(a); if(*--ms.end()<=n-2){ assert(num>=0); cout<<0<=0){ cout<<*--ms.end()-(n-2)<(0,-(num+pre)); assert(num+t+pre>=0); while(t>0 and num+(t-1)+pre>=0) t--; auto check=[&](Int v){return num+t+v>=0;}; Int ans=(n-1)*t+seg.find(0,check)+1; cout<