#ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include using namespace std; #define pass (void)0 #define INF (1<<30)-1 #define INFLL (1LL<<60)-1 #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--) #define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define repr2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((int)(x).size()) #define YesNo(cond) cout << ((cond) ? "Yes\n" : "No\n") #define YESNO(cond) cout << ((cond) ? "YES\n" : "NO\n") using ll = long long; using pii = pair; using pll = pair; using vi = vector; using vl = vector; using vvi = vector; using vvl = vector; template void print(const T& value) { cout << value << "\n"; } template void print(const vector& vec) { for (auto& v : vec) cout << v << " "; cout << "\n"; } template void input(vector& vec) { for (auto& v : vec) cin >> v; }; template bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; } template bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; } #include using namespace atcoder; using mint = modint998244353; using vm = vector; // https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py template class SortedMultiset { private: static constexpr int BUCKET_RATIO = 16; static constexpr int SPLIT_RATIO = 24; vector> a; int sz = 0; void build(const vector& v) { int n = v.size(); sz = n; if (n == 0) { a.clear(); return; } int num_bucket = (int)ceil(sqrt((double)n / BUCKET_RATIO)); a.resize(num_bucket); for (int i = 0; i < num_bucket; i++) { int l = n * i / num_bucket; int r = n * (i + 1) / num_bucket; a[i] = vector(v.begin() + l, v.begin() + r); } } pair position(const T& x) const { // return {bucket index, position in bucket} for (int i = 0; i < (int)a.size(); i++) { if (x <= a[i].back()) { return {i, lower_bound(a[i].begin(), a[i].end(), x) - a[i].begin()}; } } int i = (int)a.size() - 1; return {i, (int)a[i].size()}; } T pop_internal(int b, int i) { T ans = a[b][i]; a[b].erase(a[b].begin() + i); sz--; if (a[b].empty()) { a.erase(a.begin() + b); } return ans; } public: SortedMultiset() {} SortedMultiset(vector v) { sort(v.begin(), v.end()); build(v); } int size() const { return sz; } bool empty() const { return sz == 0; } bool contains(const T& x) const { if (sz == 0) return false; auto [b, i] = position(x); return i < (int)a[b].size() && a[b][i] == x; } int count(const T& x) const { return index_right(x) - index(x); } void add(const T& x) { if (sz == 0) { a = {{x}}; sz = 1; return; } auto [b, i] = position(x); a[b].insert(a[b].begin() + i, x); sz++; if ((int)a[b].size() > (int)a.size() * SPLIT_RATIO) { int mid = a[b].size() >> 1; vector left(a[b].begin(), a[b].begin() + mid); vector right(a[b].begin() + mid, a[b].end()); a.erase(a.begin() + b); a.insert(a.begin() + b, right); a.insert(a.begin() + b, left); } } bool discard(const T& x) { if (sz == 0) return false; auto [b, i] = position(x); if (i == (int)a[b].size() || a[b][i] != x) { return false; } pop_internal(b, i); return true; } optional lt(const T& x) const { for (int i = (int)a.size() - 1; i >= 0; i--) { if (a[i][0] < x) { auto it = lower_bound(a[i].begin(), a[i].end(), x); --it; return *it; } } return nullopt; } optional le(const T& x) const { for (int i = (int)a.size() - 1; i >= 0; i--) { if (a[i][0] <= x) { auto it = upper_bound(a[i].begin(), a[i].end(), x); --it; return *it; } } return nullopt; } optional gt(const T& x) const { for (int i = 0; i < (int)a.size(); i++) { if (a[i].back() > x) { auto it = upper_bound(a[i].begin(), a[i].end(), x); return *it; } } return nullopt; } optional ge(const T& x) const { for (int i = 0; i < (int)a.size(); i++) { if (a[i].back() >= x) { auto it = lower_bound(a[i].begin(), a[i].end(), x); return *it; } } return nullopt; } T operator[](int i) const { if (i < 0) i += sz; for (auto &bucket : a) { if (i < (int)bucket.size()) { return bucket[i]; } i -= bucket.size(); } throw out_of_range("index out of range"); } T pop(int i = -1) { if (i < 0) i += sz; for (int b = 0; b < (int)a.size(); b++) { if (i < (int)a[b].size()) { return pop_internal(b, i); } i -= a[b].size(); } throw out_of_range("index out of range"); } int index(const T& x) const { int ans = 0; for (auto &bucket : a) { if (bucket.back() >= x) { return ans + (lower_bound(bucket.begin(), bucket.end(), x) - bucket.begin()); } ans += bucket.size(); } return ans; } int index_right(const T& x) const { int ans = 0; for (auto &bucket : a) { if (bucket.back() > x) { return ans + (upper_bound(bucket.begin(), bucket.end(), x) - bucket.begin()); } ans += bucket.size(); } return ans; } vector to_vector() const { vector res; for (auto &bucket : a) { for (auto &x : bucket) { res.push_back(x); } } return res; } }; struct BITSortedMultiset { int N; vector> bit; BITSortedMultiset(int N) : N(N) { bit.assign(N+1, SortedMultiset ()); } void insert(int p, ll x) { for (int i = p+1; i <= N; i += i&-i) { bit[i].add(x); } } void remove(int p, ll x) { for (int i = p+1; i <= N; i += i&-i) { bit[i].discard(x); } } // [0,r) 内の x以上の個数 ll prefix_count_ge(int r, ll x) const { ll ans = 0; for (int i = r; i > 0; i -= i&-i) { ans += bit[i].size() - bit[i].index(x); } return ans; } // [0,r) 内の x以下の個数 ll prefix_count_le(int r, ll x) const { ll ans = 0; for (int i = r; i > 0; i -= i&-i) { ans += bit[i].index_right(x); } return ans; } // [0,r) 内の x以上y以下の個数 ll prefix_count_range(int r, ll x, ll y) const { if (x > y) return 0; ll ans = 0; for (int i = r; i > 0; i -= i&-i) { ans += bit[i].index_right(y) - bit[i].index(x); } return ans; } // [l,r) 内の x以上の個数 ll count_ge(int l, int r, ll x) const { return prefix_count_ge(r, x) - prefix_count_ge(l, x); } // [l,r) 内の x以下の個数 ll count_le(int l, int r, ll x) const { return prefix_count_le(r, x) - prefix_count_le(l, x); } // [l,r) 内の x以上y以下の個数 ll count_range(int l, int r, ll x, ll y) const { if (x > y) return 0; return prefix_count_range(r, x, y) - prefix_count_range(l, x, y); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); ll N; cin >> N; vector> query; vl IDX(1000000, -1); rep (i, N) { ll L, R; cin >> L >> R; query.push_back({L-1, 0, i}); query.push_back({R-1, 1, i}); IDX[L-1] = R; } sort(all(query)); BITSortedMultiset B(1000000); ll ans = 0; for (auto [idx, a, qidx] : query) { if (a == 0) { ans += B.count_le(IDX[idx], 1000000, qidx); B.insert(IDX[idx], qidx); } else { B.remove(idx, qidx); } } print(ans); }