//header #ifdef LOCAL #include "cxx-prettyprint-master/prettyprint.hpp" #define debug(x) cout << x << endl #else #define debug(...) 42 #endif #pragma GCC optimize("Ofast") #include //types using namespace std; using ll = long long; using ul = unsigned long long; using ld = long double; typedef pair < ll , ll > Pl; typedef pair < int, int > Pi; typedef vector vl; typedef vector vi; template< typename T > using mat = vector< vector< T > >; template< int mod > struct modint { int x; modint() : x(0) {} modint(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} modint &operator+=(const modint &p) { if((x += p.x) >= mod) x -= mod; return *this; } modint &operator-=(const modint &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } modint &operator*=(const modint &p) { x = (int) (1LL * x * p.x % mod); return *this; } modint &operator/=(const modint &p) { *this *= p.inverse(); return *this; } modint operator-() const { return modint(-x); } modint operator+(const modint &p) const { return modint(*this) += p; } modint operator-(const modint &p) const { return modint(*this) -= p; } modint operator*(const modint &p) const { return modint(*this) *= p; } modint operator/(const modint &p) const { return modint(*this) /= p; } bool operator==(const modint &p) const { return x == p.x; } bool operator!=(const modint &p) const { return x != p.x; } modint inverse() const { int a = x, b = mod, u = 1, v = 0, t; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return modint(u); } modint pow(int64_t n) const { modint ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const modint &p) { return os << p.x; } friend istream &operator>>(istream &is, modint &a) { int64_t t; is >> t; a = modint< mod >(t); return (is); } static int get_mod() { return mod; } }; //abreviations #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define rep_(i, a_, b_, a, b, ...) for (int i = (a), max_i = (b); i < max_i; i++) #define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define rrep_(i, a_, b_, a, b, ...) for (int i = (b-1), min_i = (a); i >= min_i; i--) #define rrep(i, ...) rrep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define SZ(x) ((int)(x).size()) #define pb(x) push_back(x) #define eb(x) emplace_back(x) #define mp make_pair #define print(x) cout << x << endl #define vsum(x) accumulate(x, 0LL) #define vmax(a) *max_element(all(a)) #define vmin(a) *min_element(all(a)) #define lb(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define ub(c, x) distance((c).begin(), upper_bound(all(c), (x))) //functions ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } ll lcm(ll a, ll b) { return a/gcd(a, b)*b;} templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b T mypow(T x, ll n) { T ret = 1; while(n > 0) { if(n & 1) (ret *= x); (x *= x); n >>= 1; } return ret; } ll modpow(ll x, ll n, const ll mod) { ll ret = 1; while(n > 0) { if(n & 1) (ret *= x); (x *= x); n >>= 1; x%=mod; ret%=mod; } return ret; } uint64_t my_rand(void) { static uint64_t x = 88172645463325252ULL; x = x ^ (x << 13); x = x ^ (x >> 7); return x = x ^ (x << 17); } //graph template template< typename T > struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template< typename T > using Edges = vector< edge< T > >; template< typename T > using WeightedGraph = vector< Edges< T > >; using UnWeightedGraph = vector< vector< int > >; //constant //#define inf 1000000005LL #define inf 4000000000000000005LL #define mod 1000000007LL #define endl '\n' typedef modint mint; const long double eps = 0.0001; const long double PI = 3.141592653589793; //library //実装上当然正の値しか入らないことに注意!!!!! struct SuccinctIndexableDictionary { size_t length; size_t blocks; vector< unsigned > bit, sum; SuccinctIndexableDictionary() = default; SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) { bit.assign(blocks, 0U); sum.assign(blocks, 0U); } void set(int k) { bit[k >> 5] |= 1U << (k & 31); } void build() { sum[0] = 0U; for(int i = 1; i < blocks; i++) { sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]); } } bool operator[](int k) { return (bool((bit[k >> 5] >> (k & 31)) & 1)); } int rank(int k) { return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1))); } int rank(bool val, int k) { return (val ? rank(k) : k - rank(k)); } }; template< typename T, int MAXLOG > struct WaveletMatrix { size_t length; SuccinctIndexableDictionary matrix[MAXLOG]; int mid[MAXLOG]; WaveletMatrix() = default; WaveletMatrix(vector< T > v) : length(v.size()) { vector< T > l(length), r(length); for(int level = MAXLOG - 1; level >= 0; level--) { matrix[level] = SuccinctIndexableDictionary(length + 1); int left = 0, right = 0; for(int i = 0; i < length; i++) { if(((v[i] >> level) & 1)) { matrix[level].set(i); r[right++] = v[i]; } else { l[left++] = v[i]; } } mid[level] = left; matrix[level].build(); v.swap(l); for(int i = 0; i < right; i++) { v[left + i] = r[i]; } } } pair< int, int > succ(bool f, int l, int r, int level) { return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f}; } // v[k] T access(int k) { T ret = 0; for(int level = MAXLOG - 1; level >= 0; level--) { bool f = matrix[level][k]; if(f) ret |= T(1) << level; k = matrix[level].rank(f, k) + mid[level] * f; } return ret; } T operator[](const int &k) { return access(k); } // count i s.t. (0 <= i < r) && v[i] == x int rank(const T &x, int r) { int l = 0; for(int level = MAXLOG - 1; level >= 0; level--) { tie(l, r) = succ((x >> level) & 1, l, r, level); } return r - l; } // k-th(0-indexed) smallest number in v[l,r) T kth_smallest(int l, int r, int k) { assert(0 <= k && k < r - l); T ret = 0; for(int level = MAXLOG - 1; level >= 0; level--) { int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l); bool f = cnt <= k; if(f) { ret |= T(1) << level; k -= cnt; } tie(l, r) = succ(f, l, r, level); } return ret; } // k-th(0-indexed) largest number in v[l,r) T kth_largest(int l, int r, int k) { return kth_smallest(l, r, r - l - k - 1); } // count i s.t. (l <= i < r) && (v[i] < upper) int range_freq(int l, int r, T upper) { int ret = 0; for(int level = MAXLOG - 1; level >= 0; level--) { bool f = ((upper >> level) & 1); if(f) ret += matrix[level].rank(false, r) - matrix[level].rank(false, l); tie(l, r) = succ(f, l, r, level); } return ret; } // count i s.t. (l <= i < r) && (lower <= v[i] < upper) int range_freq(int l, int r, T lower, T upper) { return range_freq(l, r, upper) - range_freq(l, r, lower); } // max v[i] s.t. (l <= i < r) && (v[i] < upper) T prev_value(int l, int r, T upper) { int cnt = range_freq(l, r, upper); return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1); } // min v[i] s.t. (l <= i < r) && (lower <= v[i]) T next_value(int l, int r, T lower) { int cnt = range_freq(l, r, lower); return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt); } }; int main(){ cin.tie(0); ios::sync_with_stdio(0); cout << setprecision(20); int n; cin>>n; vl a(n), l(n), r(n); rep(i, n)cin>>a[i], a[i]+=mod; rep(i, n)cin>>l[i]>>r[i]; vi id(n); iota(all(id), 0); sort(all(id), [&](ll a, ll b){return a wm(v); ll ans = 0; rep(i, n){ int j = id[i]; int k = ub(a, a[j]+r[j]); ans+=wm.range_freq(i+1, k, a[j]+1); } print(ans); }