#include using namespace std; using ll=long long; using pii=pair; #define all(a) a.begin(),a.end() #define pb push_back #define sz(a) ((int)a.size()) const int maxn=200005,mod=1000000007; int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;} int sub(int x, int y){x-=y; if(x<0) x+=mod; return x;} struct BIT{ int val[maxn]; vector vec; void modify(int p, int x, bool flag=1){if(flag) vec.pb({p,x}); for(++p; p> vec; vector vec1; void solve1(int l, int r){ if(l==r) return; int mid=l+r>>1; solve1(l,mid),solve1(mid+1,r); vec1.resize(r-l+1); for(int i=l; i<=r; ++i) vec1[i-l]=i; sort(all(vec1),[&](int i, int j){return vec[i][1]!=vec[j][1]?vec[i][1]vec[j][2];}); bit1.clear(),bit2.clear(); for(int i: vec1){ if(i<=mid) bit1.modify(vec[i][2],1),bit2.modify(vec[i][2],vec[i][0]); else res=add(res,sub(1ll*bit1.query(vec[i][2]-1)*vec[i][0]%mod,bit2.query(vec[i][2]-1))); } } void solve2(){ sort(all(vec)); vector tmp; for(int i=0; i> n; for(int i=0; i> a[i]; for(int i=0; i> b[i]; vec.resize(n); for(int i=0; i