### DCP Offline O(n log² n)

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6 + 2;

struct DSU {
    int p[N], s[N];
    int *ptr[N], val[N], size;

    DSU() {
        fill_n(s, N, 1);
        iota(p, p + N, 0);
        size = 0;
    }

    void save(int &x) {
        ptr[size] = &x;
        val[size] = x;
        ++size;
    }

    int get(int x) {
        while (p[x] != x) {
            x = p[x];
        }
        return x;
    }

    void merge(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return;
        }
        if (s[x] > s[y]) {
            swap(x, y);
        }
        save(p[x]);
        save(s[y]);
        p[x] = y;
        s[y] += s[x];
    }

    void back_to(int s) {
        while (size > s) {
            --size;
            *ptr[size] = val[size];
        }
    }
} dsu;

int a[N], b[N], edges = 0;
vector<int> add[2 * N];

void add_edge(int v, int u, int tl, int tr) {
    a[edges] = v;
    b[edges] = u;
    int l = tl + N;
    int r = tr + N;
    for (; l <= r; l /= 2, r /= 2) {
        if (l % 2 == 1) {
            add[l++].push_back(edges);
        }
        if (r % 2 == 0) {
            add[r--].push_back(edges);
        }
    }
    ++edges;
}

int answer[N];

void solve(int v) {
    int saved_size = dsu.size;
    for (int e : add[v]) {
        dsu.merge(a[e], b[e]);
    }
    if (v >= N) {
        int fn = v - N;
        answer[fn] = dsu.s[dsu.get(fn)] - 1;
    } else {
        solve(2 * v);
        solve(2 * v + 1);
    }
    dsu.back_to(saved_size);
}

ll number_of_pairs(int n, const vector<vector<int>> &r, const vector<vector<int>> &u) {
    for (int i = 0; i < n; ++i) {
        int last = 0;
        for (int j = 0; j < (int)r[i].size(); ++j) {
            if (last <= i && i <= r[i][j]) {
                add_edge(i, u[i][j], last, i - 1);
                add_edge(i, u[i][j], i + 1, r[i][j]);
            } else {
                add_edge(i, u[i][j], last, r[i][j]);
            }
            last = r[i][j] + 1;
        }
    }
    solve(1);
    //for (int i = 0; i < n; ++i) {
    //  cerr << answer[i] << " ";
    //}
    //cerr << endl;
    return accumulate(answer, answer + n, (ll)0);
}

#ifdef LC
int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout <<
    number_of_pairs(4,
    {{3},{1,3},{2,3},{3}},
    {{1},{0,2},{1,3},{2}})
    << endl;
    return 0;
}
#endif