#include using namespace std; using Int = long long; template struct RangeCount{ struct BIT{ vector dat; BIT(){} BIT(int n){dat.assign(++n,0);} T sum(int k){ T res=0; for(;k;k-=k&-k) res+=dat[k]; return res; } void add(int k,T v){ for(++k;k<(int)dat.size();k+=k&-k) dat[k]+=v; } }; int n; vector > val; vector dat; RangeCount(){} RangeCount(int n_){ n=1; while(n()); dat.reserve(n<<1); } void preupdate(int a,int x){ a+=n; while(a){ val[a].emplace_back(x); a>>=1; } } void build(){ for(int i=0;i>=1; } } T calc(int k,int x,int y){ auto &v=val[k]; int p=lower_bound(v.begin(),v.end(),x)-v.begin(); int q=lower_bound(v.begin(),v.end(),y)-v.begin(); return dat[k].sum(q)-dat[k].sum(p); } // [a, b) * [x, y) T query(int a,int b,int x,int y){ T res=0; for(int l=a+n,r=b+n;l>=1,r>>=1){ if(l&1) res+=calc(l++,x,y); if(r&1) res+=calc(--r,x,y); } return res; } }; //INSERT ABOVE HERE signed main(){ int n,m; scanf("%d %d",&n,&m); vector a(n),b(n); for(int i=0;i seg(m); for(int i=0;ib[i]) swap(a[i],b[i]); seg.preupdate(a[i],b[i]); } seg.build(); long long ans=0; for(int i=0;i