#include #include using namespace std; using namespace atcoder; typedef long long int ll; typedef long double ld; typedef vector vi; typedef vector vl; typedef vector vvl; typedef vector vvvl; typedef vector vvvvl; typedef vector vb; typedef vector vvb; typedef vector vvvb; typedef vector vvvvb; typedef pair pl; typedef pair ppl; typedef pair pppl; typedef pair pppppl; #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(a) begin(a),end(a) #define sz(a) (int)(a).size() #define F first #define S second #define bs(A,x) binary_search(all(A),x) #define lb(A,x) (ll)(lower_bound(all(A),x)-A.begin()) #define ub(A,x) (ll)(upper_bound(all(A),x)-A.begin()) #define cou(A,x) (ll)(upper_bound(all(A),x)-lower_bound(all(A),x)) templateusing min_priority_queue=priority_queue,greater>; templatebool chmax(T&a,T b){if(abool chmin(T&a,T b){if(b vm; typedef vector vvm; typedef vector vvvm; typedef vector vvvvm; ostream&operator<<(ostream&os,mint a){os<>(istream&is,mint&a){int x;is>>x;a=mint(x);return is;} //*/ templateostream&operator<<(ostream&os,pairp){os<istream&operator>>(istream&is,pair&p){is>>p.F>>p.S;return is;} templateostream&operator<<(ostream&os,vectorv){rep(i,0,sz(v))os<istream&operator>>(istream&is,vector&v){for(T&in:v)is>>in;return is;} template struct segtree_2d_sparse_with_ACL{ private: size_t H,W; vector>seg; vector>E; int id(int h,int w){ if(!binary_search(E[h].begin(),E[h].end(),w))return -1; return lower_bound(E[h].begin(),E[h].end(),w)-E[h].begin(); } public: segtree_2d_sparse_with_ACL(size_t _H,size_t _W,vector>query){init(_H,_W,query);} void init(size_t _H,size_t _W,vector>query){ H=W=1; while(H<_H)H<<=1; while(W<_W)W<<=1; E.resize(2*H); seg.resize(2*H); for(auto[h,w]:query){ assert(0<=h&&h(E[i].size()); if(i)for(int j:E[i])E[i>>1].emplace_back(j); } } void set(int h,int w,S x){ assert(0<=h&&h1){ if(id(h^1,w)!=-1)x=op(x,seg[h^1].get(id(h^1,w))); h>>=1; seg[h].set(id(h,w),x); } } S get(int h,int w){ assert(0<=h&&h>=1; h2>>=1; } return res; } }; ll op(ll a,ll b){return a+b;} ll e(){return 0;} int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); ll N;cin>>N; vectorA(N); cin>>A; vector>query(N); rep(i,0,N)query[i]=make_pair(i,A[i].second); segtree_2d_sparse_with_ACLseg(1000010,1000010,query); vl I(N); iota(all(I),0); sort(all(I),[&](ll a,ll b){return A[a]