#include using namespace std; using int64 = long long; using uint64 = unsigned long long; #define repeat(i, x) for (int64 i = 0; (i) < (x); (i)++) #define rev_repeat(i, x) for (int64 i = (x) - 1; (i) >= 0; (i)--) #define countup(i, n) for (int64 i = 0; (i) <= (n); (i)++) #define countdown(i, n) for (int64 i = (n); (i) >= 0; (i)--) #define range(i, a, b) for (int64 i = (a); (i) < (b); (i)++) #define traverse(it, ctn) for (auto it = begin(ctn); (it) != end(ctn); (it)++) #define rev_traverse(it, ctn) for (auto it = rbegin(ctn); (it) != rend(ctn); (it)++) template ostream& operator<<(ostream& os, vector& vec) { os << "["; repeat (i, vec.size()) { os << (i == 0 ? "" : ", ") << vec[i]; } os << "]"; return os; } template ostream& operator<<(ostream& os, pair& p) { os << "(" << p.first << ", " << p.second << ")"; return os; } template ostream& operator<<(ostream& os, set& s) { os << "{"; traverse (it, s) { if (it != s.begin()) os << ", "; os << *it; } os << "}"; return os; } template ostream& operator<<(ostream& os, map& m) { os << "{"; traverse (it, m) { if (it != m.begin()) os << ", "; os << it->first << ": " << it->second; } os << "}"; return os; } // // _______ _____ _______ _____ _______ _______ _____ _______ _____ _ _ _______ // | | | | | | |_____] |______ | | | | \ / |______ // |_____ |_____| | | | | |______ | __|__ | __|__ \/ |______ // // _____ ______ _____ ______ ______ _______ _______ _______ _____ __ _ ______ / // |_____] |_____/ | | | ____ |_____/ |_____| | | | | | | | | \ | | ____ / // | | \_ |_____| |_____| | \_ | | | | | | | | __|__ | \_| |_____| . // using Event = tuple; // (座標, イベントの種類, Aにおける添字) template struct fenwick_tree { int n; std::vector x; fenwick_tree(int n_ = 0) : n(n_), x(n + 1, 0) {} int size() const { return n; } T sum(int r) const { T S = 0; for (r = r - 1; r >= 0; r = (r & (r + 1)) - 1) S += x[r]; return S; } T sum(int l, int r) const { return sum(r) - sum(l); } void add(int k, const T &a) { for (; k < n; k |= k + 1) x[k] += a; } void set(int k, const T &a) { add(k, a - sum(k, k + 1)); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; vector A(N); repeat (i, N) { cin >> A[i]; } vector L(N), R(N); vector events; // (座標、イベントの種類) repeat (i, N) { cin >> L[i] >> R[i]; events.emplace_back(A[i] - L[i], 0, i); events.emplace_back(A[i], 1, i); } sort(events.begin(), events.end()); fenwick_tree ft(N); int64 ans = 0; for (auto& ev : events) { int idx = get<2>(ev); if (get<1>(ev) == 0) { ft.add(idx, 1); } else { // A[k] <= A[i] + R[i]を満たす最大のkを見つける int k = (upper_bound(A.begin(), A.end(), A[idx] + R[idx]) - A.begin()) - 1; ans += ft.sum(idx + 1, k + 1); } } cout << ans << endl; return 0; }