/*********************************************************************
    程序名: 宠物收养所
    版权:
    作者: sanhai
    日期: 2025-08-19 10:51
    说明:
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
const int N = 80005, inf=0x3f3f3f3f;
long long ans;

struct Tree {
	int dat[N], val[N], siz[N], son[N][2];
	int rt;
	void split(int p, int x, int &l, int &r) {
    if (!p) { l = r = 0; return; }
    if (val[p] <= x) {
        l = p;
        split(son[p][1], x, son[p][1], r);
    } else {
        r = p;
        split(son[p][0], x, l, son[p][0]);
    }
    siz[p] = siz[son[p][0]] + siz[son[p][1]] + 1;
}

int merge(int l, int r) {
    if (!l || !r) return l + r;
    if (dat[l] > dat[r]) {
        son[l][1] = merge(son[l][1], r);
        siz[l] = siz[son[l][0]] + siz[son[l][1]] + 1;
        return l;
    } else {
        son[r][0] = merge(l, son[r][0]);
        siz[r] = siz[son[r][0]] + siz[son[r][1]] + 1;
        return r;
    }
}

void insert(int x) {
    static int idx = 0;
    int l, r;
    split(rt, x, l, r);
    val[++idx] = x;
    dat[idx] = rand();
    siz[idx] = 1;
    rt = merge(merge(l, idx), r);
}

void remove(int x) {
    int l, r, p;
    split(rt, x, l, r);
    split(l, x-1, l, p);
    if (p) {
        p = merge(son[p][0], son[p][1]);
        rt = merge(merge(l, p), r);
    } else {
        rt = merge(l, r);
    }
}

int rnk(int x) {
    int l, r;
    split(rt, x-1, l, r);
    int res = siz[l] + 1;
    rt = merge(l, r);
    return res;
}

int kth(int p, int k) {
    if (k == siz[son[p][0]] + 1) return p;
    if (k <= siz[son[p][0]]) return kth(son[p][0], k);
    return kth(son[p][1], k - siz[son[p][0]] - 1);
}

int get_pre(int x) {
    int l, r;
    split(rt, x-1, l, r);
    int res = -inf;
    if (l) res = val[kth(l, siz[l])];
    rt = merge(l, r);
    return res;
}

int get_nxt(int x) {
    int l, r;
    split(rt, x, l, r);
    int res = inf;
    if (r) res = val[kth(r, 1)];
    rt = merge(l, r);
    return res;
}

} cat, human;

int main() {
	srand(time(NULL));
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		if (a == 0) {
			if (human.siz[human.rt]) {
				int pre = human.get_pre(b);
				int nxt = human.get_nxt(b);
				if (b - pre <= nxt - b) {
					ans += abs(b - pre);
					human.remove(pre);
				} else {
					ans += abs(nxt - b);
					human.remove(nxt);
				}
			} else
				cat.insert(b);

		} else {
			if (cat.siz[cat.rt]) {
				int pre = cat.get_pre(b);
				int nxt = cat.get_nxt(b);
				if (b - pre <= nxt - b) {
					ans += abs(b - pre);
					cat.remove(pre);
				} else {
					ans += abs(nxt - b);
					cat.remove(nxt);
				}
			} else
				human.insert(b);
		}
		ans %= 1000000;
	}
	cout << ans % 1000000;

	return 0;
}

悬赏5个币