#include <bits/stdc++.h>

using ll = long long;

// assume -mod <= x < 2mod
constexpr int mod = 1000000;
constexpr ll inf = 1e18;

int norm(int x) {
    if (x < 0) { x += mod; }
    if (x >= mod) { x -= mod; }
    return x;
}
template<class T>
T power(T a, ll b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0): x(norm(x)) {}
    Z(ll x): x(norm(x% mod)) {}
    int val() const { return x; }
    Z operator-() const { return Z(norm(mod - x)); }
    Z inv() const {
        assert(x != 0);
        return power(*this, mod - 2);
    }
    Z& operator*=(const Z& rhs) {
        x = ll(x) * rhs.x % mod;
        return *this;
    }
    Z& operator+=(const Z& rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z& operator-=(const Z& rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z& operator/=(const Z& rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z& lhs, const Z& rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z& lhs, const Z& rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z& lhs, const Z& rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z& lhs, const Z& rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream& operator>>(std::istream& is, Z& a) {
        ll v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream& operator<<(std::ostream& os, const Z& a) {
        return os << a.val();
    }
};

struct Node {
    Node* ch[2];
    Node* p;
    ll v;
    int size;

    Node(ll v, Node* p = nullptr): ch{ nullptr, nullptr }, p(p), v(v), size(1) {}

    void pull() {
        size = 1;
        if (ch[0] != nullptr) {
            size += ch[0]->size;
        }
        if (ch[1] != nullptr) {
            size += ch[1]->size;
        }
    }

    void rotate() {
        Node* q = p;
        bool x = !pos();
        q->ch[!x] = ch[x];
        if (ch[x] != nullptr) {
            ch[x]->p = q;
        }
        p = q->p;
        if (q->p != nullptr) {
            q->p->ch[q->pos()] = this;
        }
        ch[x] = q;
        q->p = this;
        q->pull();
        pull();
    }

    bool pos() {
        return p->ch[1] == this;
    }

    void splay(Node* g = nullptr) {
        while (p != g) {
            if (p->p != g) {
                if (pos() == p->pos()) {
                    p->rotate();
                }
                else {
                    rotate();
                }
            }
            rotate();
        }
        pull();
    }
} *root[2], * L[2], * R[2];

Node* select(Node* t, int k) {
    if (t->ch[0] != nullptr) {
        if (k < t->ch[0]->size) {
            return select(t->ch[0], k);
        }
        else {
            k -= t->ch[0]->size;
        }
    }
    if (k == 0) {
        return t;
    }
    k--;
    return select(t->ch[1], k);
}

Node* insert(Node*& u, ll v) {
    Node* p = nullptr;
    while (u) {
        p = u;
        u = u->ch[v > u->v];
    }
    u = new Node(v, p);
    if (p) {
        p->ch[v > p->v] = u;
    }
    u->splay();
    return u;
}

Node* findPrev(Node* u, int v) {
    Node* ans = nullptr;
    ll res = -1;
    while (u) {
        if (u->v <= v) {
            if (u->v > res) {
                res = u->v;
                ans = u;
            }
            u = u->ch[1];
        }
        else {
            u = u->ch[0];
        }
    }
    return ans;
}

Node* findNext(Node* u, int v) {
    Node* ans = nullptr;
    ll res = inf + 1;
    while (u) {
        if (u->v >= v) {
            if (u->v < res) {
                res = u->v;
                ans = u;
            }
            u = u->ch[0];
        }
        else {
            u = u->ch[1];
        }
    }
    return ans;
}

Node* Pre(Node* u, int v) {
    Node* ans = nullptr;
    ll res = -1;
    while (u) {
        if (u->v < v) {
            if (u->v > res) {
                res = u->v;
                ans = u;
            }
            u = u->ch[1];
        }
        else {
            u = u->ch[0];
        }
    }
    return ans;
}

Node* Nxt(Node* u, int v) {
    Node* ans = nullptr;
    ll res = inf + 1;
    while (u) {
        if (u->v > v) {
            if (u->v < res) {
                res = u->v;
                ans = u;
            }
            u = u->ch[0];
        }
        else {
            u = u->ch[1];
        }
    }
    return ans;
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);

    int n;
    std::cin >> n;

    Z ans = 0;

    for (int i : {0, 1}) {
        L[i] = insert(root[i], 0);
        R[i] = insert(root[i], inf);
    }

    for (int i = 0; i < n; i++) {
        int k, v;
        std::cin >> k >> v;
        assert(v > 0);
        if (root[k ^ 1]->size == 2) {
            insert(root[k], v);
        }
        else {
            auto pre = findPrev(root[k ^ 1], v);
            auto nxt = findNext(root[k ^ 1], v);
            if (pre->v == 0) {
                // 从root[k ^ 1] 中 删掉nxt
                ans += std::abs(v - nxt->v);
                auto l = Pre(root[k ^ 1], nxt->v);
                auto r = Nxt(root[k ^ 1], nxt->v);
                if (l == nullptr) {
                    l = L[k ^ 1];
                }
                if (r == nullptr) {
                    r = R[k ^ 1];
                }
                l->splay();
                r->splay(l);
                r->ch[0] = nullptr;
                r->pull();
                l->pull();
                root[k ^ 1] = l;
            }
            else if (nxt->v == inf) {
                // 从root[k ^ 1] 中 删掉pre
                ans += std::abs(v - pre->v);
                auto l = Pre(root[k ^ 1], pre->v);
                auto r = Nxt(root[k ^ 1], pre->v);
                if (l == nullptr) {
                    l = L[k ^ 1];
                }
                if (r == nullptr) {
                    r = R[k ^ 1];
                }
                assert(l);
                assert(r);
                l->splay();
                r->splay(l);
                r->ch[0] = nullptr;
                r->pull();
                l->pull();
                root[k ^ 1] = l;
            }
            else {
                if (v - pre->v > nxt->v - v) {
                    std::swap(pre, nxt);
                }
                // 从root[k ^ 1] 中 删掉pre
                ans += std::abs(v - pre->v);
                auto l = Pre(root[k ^ 1], pre->v);
                auto r = Nxt(root[k ^ 1], pre->v);
                if (l == nullptr) {
                    l = L[k ^ 1];
                }
                if (r == nullptr) {
                    r = R[k ^ 1];
                }
                assert(l);
                assert(r);
                l->splay();
                r->splay(l);
                r->ch[0] = nullptr;
                r->pull();
                l->pull();
                root[k ^ 1] = l;
            }
        }
    }

    std::cout << ans << '\n';

    return 0;
}

如图所示的代码会在第9个点RE