#include #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; using pii = pair; using vi = vector; template ostream& operator<<(ostream& os, const vector& v) { os << "sz=" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } constexpr ll MOD = 1e9 + 7; template constexpr T INF = numeric_limits::max() / 100; struct Sorted { using T = vector; struct AccMonoid { T operator()(const T& a, const T& b) const { T c(a.size() + b.size()); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); return c; } static T identity() { return vector{}; } }; }; template class SegmentTree { public: using BaseAlgebra = Base; using AccMonoid = typename BaseAlgebra::AccMonoid; using T = typename BaseAlgebra::T; SegmentTree(const std::vector& val) : data_num(val.size()), height(__lg(2 * data_num - 1)), size(1 << (1 + height)), half(size >> 1), value(size) { for (int data = 0; data < half; data++) { if (data < data_num) { value[data + half] = val[data]; } else { value[data + half] = AccMonoid::identity(); } } for (int node = half - 1; node >= 1; node--) { value[node] = acc(value[2 * node], value[2 * node + 1]); } } int query(const int a, const int b, const ll v) const { assert(0 <= a and a < b and b <= data_num); return queryRec(1, 0, half, a, b, v); } private: int queryRec(const int int_index, const int int_left, const int int_right, const int mod_left, const int mod_right, const ll v) const { if (mod_left <= int_left and int_right <= mod_right) { return upper_bound(value[int_index].begin(), value[int_index].end(), v) - value[int_index].begin(); } else if (int_right <= mod_left or mod_right <= int_left) { return 0; } else { return queryRec(2 * int_index, int_left, (int_left + int_right) / 2, mod_left, mod_right, v) + queryRec(2 * int_index + 1, (int_left + int_right) / 2, int_right, mod_left, mod_right, v); } } const int data_num; // Num of valid data on leaves. const int height; const int size; const int half; vector value; // Tree for value(length: size) const AccMonoid acc{}; }; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } vector L(N); vector A_R(N); vector> A_L(N, vector(1, 0)); for (int i = 0; i < N; i++) { ll R; cin >> L[i] >> R; A_R[i] = A[i] + R; A_L[i][0] = A[i] - L[i]; } SegmentTree seg(A_L); ll sum = 0; for (int i = 0; i < N; i++) { const int upper = upper_bound(A.begin(), A.end(), A_R[i]) - A.begin(); if (i + 1 < upper) { sum += (ll)seg.query(i + 1, upper, A[i]); } } cout << sum << endl; return 0; }