#include using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const pair&p){ os< ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,pair&p){ is>>p.first>>p.second; return is; } template istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } template struct BinaryIndexedTree{ vector data; BinaryIndexedTree()=default; BinaryIndexedTree(int sz):data(sz+1,0){} BinaryIndexedTree(const vector &a):data(a.size()+1,0){ for(int i=0;i<(int)a.size();i++)data[i+1]=a[i]; for(int i=1;i<(int)data.size();i++){ int j=i+(i&-i); if(j<(int)data.size()) data[j]+=data[i]; } } void add(int k,const T &x){for(++k;k<(int)data.size();k+=(k&-k)) data[k]+=x;} // sum [0,k) T sum(int k){ T ret=T(); for(;k>0;k-=(k&-k))ret+=data[k]; return ret; } // sum [l,r) T query(int l,int r){ return sum(r)-sum(l); } T operator[](const int &k){return query(k,k+1);} // sum[0,i)>=xとなる最小のi int lower_bound(T x){ int r=1,i=0; while(r<(int)data.size())r<<=1; for(;r>0;r>>=1)if(i+r<(int)data.size() and data[i+r] struct RangeTree{ vector xs; vector ys; int sz,ysz; vector> seg; RangeTree(vector xs_,vector ys_):xs(xs_),ys(ys_){ sort(begin(xs),end(xs)); xs.erase(unique(begin(xs),end(xs)),end(xs)); sort(begin(ys),end(ys)); ys.erase(unique(begin(ys),end(ys)),end(ys)); sz=1;ysz=(int)ys.size(); while(sz<(int)xs.size()) sz<<=1; seg.assign(2*sz,BinaryIndexedTree(ysz)); } // 先読みさせてない値を入れない void add(Tx x,Ty y){ int k=lower_bound(begin(xs),end(xs),x)-begin(xs); int yi=lower_bound(begin(ys),end(ys),y)-begin(ys); k+=sz; for(;k;k>>=1) seg[k].add(yi,1); } void erase(Tx x,Ty y){ int k=lower_bound(begin(xs),end(xs),x)-begin(xs); int yi=lower_bound(begin(ys),end(ys),y)-begin(ys); k+=sz; for(;k;k>>=1) seg[k].add(yi,-1); } // これは先読みしていなくてもかまわない int count(Tx xl,Tx xr,Ty yl,Ty yh){ int l=lower_bound(begin(xs),end(xs),xl)-begin(xs); int r=lower_bound(begin(xs),end(xs),xr)-begin(xs); int lw=lower_bound(begin(ys),end(ys),yl)-begin(ys); int hi=lower_bound(begin(ys),end(ys),yh)-begin(ys); l+=sz,r+=sz; int ret=0; for(;l>=1,r>>=1){ if(l&1){ ret+=seg[l].query(lw,hi); l++; } if(r&1){ r--; ret+=seg[r].query(lw,hi); } } return ret; } }; void solve(){ int n;cin>>n; vector a(n),l(n),r(n),b(n); cin>>a; rep(i,n) cin>>l[i]>>r[i]; rep(i,n) b[i]=a[i]+r[i]; RangeTree seg(a,b); ll res=0; rep(i,n){ res+=seg.count(a[i]-l[i],LINF,a[i],LINF); seg.add(a[i],a[i]+r[i]); } cout<