#include #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)< P; typedef pair pll; typedef vector vi; typedef vector vvi; typedef vector vl; typedef vector vvl; typedef vector vd; typedef vector

vp; typedef vector vs; const int MAX_N = 100005; #define MAX_BIT 64 struct BitRank { // block: bit 列を管理, count: block ごとに立っている 1 の数を管理 vector block; vector count; BitRank(){} void resize(int num) { block.resize((num + 1) / MAX_BIT + 1, 0); count.resize((int)block.size(), 0); } // i ビット目を val(0,1) にセット inline void set(int i, unsigned long long val) { block[i/MAX_BIT] |= (val << (i % MAX_BIT)); } void build() { for(int i = 1; i < (int)block.size(); i++){ count[i] = count[i-1] + __builtin_popcountll(block[i-1]); } } // [0, i) ビットの 1 の数 inline int rank1(int i) { return count[i/MAX_BIT] + ((i % MAX_BIT) ? __builtin_popcountll(block[i/MAX_BIT] << (MAX_BIT-i%MAX_BIT)) : 0); } // [j, i) ビットの 1 の数 inline int rank1(int i, int j) { return rank1(j) - rank1(i); } // [0, i) ビットの 0 の数 inline int rank0(int i) { return i - rank1(i); } // [j, i) ビットの 0 の数 inline int rank0(int i, int j) { return rank0(j) - rank0(i); } }; class WaveletMatrix { private: int height; vector B; vector pos; public: WaveletMatrix(){} WaveletMatrix(vector& vec) : WaveletMatrix(vec, *max_element(vec.begin(), vec.end()) + 1) {} // sigma:文字の種類数 WaveletMatrix(vector& vec, int sigma){ init(vec, sigma); } void init(vector& vec, int sigma){ height = (sigma == 1) ? 1 : (MAX_BIT - __builtin_clzll(sigma-1)); B.resize(height), pos.resize(height); for(int i = 0; i < height; i++){ B[i].resize((int)vec.size()); for(int j = 0; j < (int)vec.size(); j++) { B[i].set(j, get(vec[j], height - i - 1)); } B[i].build(); auto it = stable_partition(vec.begin(), vec.end(), [&](int c) { return !get(c, height - i - 1); }); pos[i] = it - vec.begin(); } } // val の i ビット目の値を返す(0,1) inline int get(int val, int i) { return val >> i & 1; } // [l, r) の間に現れる値 val の数 int rank(int val, int l, int r) { return rank(val, r) - rank(val, l); } // [0, i) の間に現れる値 val の数 int rank(int val, int i) { int p = 0; for(int j = 0; j < height; j++){ if(get(val, height - j - 1)){ p = pos[j] + B[j].rank1(p); i = pos[j] + B[j].rank1(i); }else{ p = B[j].rank0(p); i = B[j].rank0(i); } } return i - p; } // [l, r) の k(1,2,3...) 番目に小さい値を返す int quantile(int k, int l, int r) { int res = 0; for(int i = 0; i < height; i++){ int j = B[i].rank0(l, r); if(j >= k){ l = B[i].rank0(l); r = B[i].rank0(r); }else{ l = pos[i] + B[i].rank1(l); r = pos[i] + B[i].rank1(r); k -= j; res |= (1 << (height - i - 1)); } } return res; } // [l,r) で値が [a,b) 内に含まれる数を返す int rangefreq(int l, int r, int a, int b) { return rangefreq(l, r, a, b, 0, 1 << height, 0); } int rangefreq(int i, int j, int a, int b, int l, int r, int x) { if(i == j || r <= a || b <= l) return 0; int mid = (l + r) >> 1; if(a <= l && r <= b){ return j - i; }else{ int left = rangefreq(B[x].rank0(i),B[x].rank0(j),a,b,l,mid,x+1); int right = rangefreq(pos[x]+B[x].rank1(i),pos[x]+B[x].rank1(j),a,b,mid,r,x+1); return left + right; } } }; template class OrthogonalRangeCount { private: using ptt = pair; int sz; vector X, Y; WaveletMatrix wm; public: OrthogonalRangeCount(vector candidate) : sz((int)candidate.size()), X(sz), Y(sz){ vector vec(sz); sort(candidate.begin(), candidate.end()); for(int i = 0; i < sz; i++){ X[i] = candidate[i].first, Y[i] = candidate[i].second; } sort(Y.begin(), Y.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end()); for(int i = 0; i < sz; i++){ vec[i] = lower_bound(Y.begin(), Y.end(), candidate[i].second) - Y.begin(); } wm.init(vec, (int)Y.size()); } // [lx,rx)×[ly,ry)の長方形領域に含まれる点の数を答える int query(T lx, T rx, T ly, T ry) { int lxid = lower_bound(X.begin(), X.end(), lx) - X.begin(); int rxid = lower_bound(X.begin(), X.end(), rx) - X.begin(); int lyid = lower_bound(Y.begin(), Y.end(), ly) - Y.begin(); int ryid = lower_bound(Y.begin(), Y.end(), ry) - Y.begin(); if(lxid >= rxid || lyid >= ryid) return 0; return wm.rangefreq(lxid, rxid, lyid, ryid); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vi a(n), l(n), r(n); vp vec(n); rep(i,n){ cin >> a[i]; } rep(i,n){ cin >> l[i] >> r[i]; vec[i] = P(a[i], a[i]-l[i]); } OrthogonalRangeCount orc(vec); ll ans = 0; rep(i,n){ ans += orc.query(a[i]+1, a[i]+r[i]+1, INT_MIN, a[i]+1); } cout << ans << "\n"; return 0; }