#include using namespace std; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a struct BIT{ Int n; vector bit; // 1-indexed BIT(Int n_):n(n_+1),bit(n+1,0){} T sum(Int i){ T s(0); for(Int x=i;x>0;x-=(x&-x)) s+=bit[x]; return s; } void add(Int i,T a){ if(i==0) return; for(Int x=i;x<=n;x+=(x&-x)) bit[x]+=a; } // [l, r) T query(Int l,Int r){ return sum(r-1)-sum(l-1); } Int lower_bound(Int w){ if(w<=0) return 0; Int x=0,r=1; while(r0;k>>=1){ if(x+k<=n&&bit[x+k]>n; vector as(n),bs(n); for(Int i=0;i>as[i]; for(Int i=0;i>bs[i]; vector rev(n+1); for(Int i=0;i cs(n); for(Int i=0;i bit(n+10); Int ans=0; for(Int i=0;i