#include <bits/stdc++.h> #define endl '\n' #define fi first #define se second #define eb emplace_back #define pb push_back #define ALL(A) A.begin(), A.end() #define FOR(i, l, r) for (int i = l; i <= r; i++) #define FOR2(i, l, r) for (int i = l; i >= r; i--) #define ce cout<<endl; using namespace std; using ll = long long; using pll = pair<ll, ll>; using pii = pair<int, int>; using str = string; using T = pair<ll,int>; const ll INF = 1e9 + 1; const int N = 1e5; struct SegmentTree { int n; vector<int> st, lz; SegmentTree(int _n) { n = _n; st.assign(4 * n + 5, 0); lz.assign(4 * n + 5, 0); } void down(int id) { if (lz[id] == 0) return; st[id * 2] += lz[id]; lz[id * 2] += lz[id]; st[id * 2 + 1] += lz[id]; lz[id * 2 + 1] += lz[id]; lz[id] = 0; } void build(int id, int l, int r, vector<int>& H) { if (l == r) { st[id] = H[l]; return; } int mid = (l + r) >> 1; build(id * 2, l, mid, H); build(id * 2 + 1, mid + 1, r, H); st[id] = max(st[id * 2], st[id * 2 + 1]); } void update(int id, int l, int r, int u, int v) { if (u > v || u > r || v < l) return; if (u <= l && r <= v) { st[id]++; lz[id]++; return; } down(id); int mid = (l + r) >> 1; update(id * 2, l, mid, u, v); update(id * 2 + 1, mid + 1, r, u, v); st[id] = max(st[id * 2], st[id * 2 + 1]); } int findFirst(int id, int l, int r, int x) { if (st[id] < x) return n + 1; if (l == r) return l; down(id); int mid = (l + r) >> 1; if (st[id * 2] >= x) return findFirst(id * 2, l, mid, x); else return findFirst(id * 2 + 1, mid + 1, r, x); } int getVal(int id, int l, int r, int pos) { if (l == r) return st[id]; down(id); int mid = (l + r) >> 1; if (pos <= mid) return getVal(id * 2, l, mid, pos); else return getVal(id * 2 + 1, mid + 1, r, pos); } void upd(int l, int r) { update(1, 1, n, l, r); } int queryFirst(int x) { return findFirst(1, 1, n, x); } int get(int pos) { return getVal(1, 1, n, pos); } }; void solve() { int n ; cin >> n; vector<pii> masts(n + 1); FOR(i,1,n) cin >> masts[i].fi >> masts[i].se; sort(masts.begin() + 1 , masts.end()); SegmentTree st(N); ll res = 0; FOR(i,1,n){ int h = masts[i].fi , k = masts[i].se; int val_k = st.get(k); int first_r = st.queryFirst(val_k); int last_r = st.queryFirst(val_k + 1) - 1 ; last_r = min(last_r , h); first_r = min(first_r , h); int num_at_val_k = k - first_r + 1; if(first_r - 1 >= 1) st.upd(1 , min(first_r - 1 , h)); st.upd(last_r - num_at_val_k + 1 ,min(last_r , h) ); } FOR(i,1,N){ int cnt= st.get(i); res += cnt * (cnt - 1) / 2 ; } cout << res <<endl; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; while (t--) { solve(); } return 0; }