splay纯板子， pre() 和 next()都返回 0;

#include<bits/stdc++.h>
#define ll long long
#define SZ idx
#define sz size

using namespace std;
template <typename T> void rd(T&x){
	x = 0; ll sign = 1; char c;
	do{ c = getchar(); if(c == '-') sign = -1;} while (!isdigit(c));
	do{ x = x * 10 + c - '0'; c = getchar();} while (isdigit(c));
	x *= sign;
}

const int N = 2e6 + 1000, MO = 1000000;

int n, idx = 0, root = 0;
int size[N], cnt[N], f[N], ch[N][2], key[N];

bool get(int x){
	return ch[f[x]][1] == x;
}

void update(int x){
	if (x){
		size[x] = cnt[x];
		size[x] += (ch[x][0] ? size[ch[x][0]] : 0) + (ch[x][1] ? size[ch[x][1]] : 0);
	}
}

void clear(int x){
	key[x] = size[x] = cnt[x] = f[x] = ch[x][0] = ch[x][1] = 0;
}

void rotate(int x){
	int y = f[x], yfa = f[y], whx = get(x);
	ch[y][whx] = ch[x][whx ^ 1];
	f[y] = x; f[x] = yfa;
	f[ch[x][whx ^ 1]] = y;
	if (yfa) ch[yfa][ch[yfa][1] == y] = x;
	update(y), update(x);
}

void splay(int x){ // x 表示 编号 
	for (int fa; fa = f[x]; rotate(x))
		if (f[fa]) 
			rotate(get(x) == get(fa) ? fa : x);
		
	root = x;
}

void insert(int x){
	if (root == 0){
		idx ++;
		size[idx] = cnt[idx] = 1;
		key[idx] = x;
		root = idx;
		ch[idx][0] = ch[idx][1] = f[idx] = 0;
		return;
	}
	int now = root, fa = 0;
	while (1){
		if (key[now] == x){
			cnt[now] ++;
			update(now), update(fa);
			splay(now);
			break;
		}
		
		fa = now;
		now = ch[now][x > key[now]];
		
		if (now == 0){
			
			idx ++;
			size[idx] = cnt[idx] = 1;
			key[idx] = x;
			f[idx] = fa;
			ch[idx][0] = ch[idx][1] = 0;
			ch[fa][x > key[fa]] = idx;
			update(fa);
			splay(idx);
			break;
		}
	}
}

int find(int x){
	int now = root, ans = 0;	
	while (1){
		if (x < key[now]){
			now = ch[now][0];
		}else {
			ans += (ch[now][0] ? size[ch[now][0]] : 0);
			if (x == key[now]){
				splay(x);
				return ans + 1;
			}	
			ans += cnt[now];
			now = ch[now][1];
		}
	}
}

int pre(){
	int now = root;
	now = ch[root][0];
	while (ch[now][1]) now = ch[now][1];
	return now;
}

int next(){
	int now = root;
	now = ch[root][1];
	while (ch[now][0]) now = ch[now][0];
	return now;
}

void del(int x){
	int ooo = find(x);
//	int now = root;
	if (cnt[root] > 1){ cnt[root] --; update(root); return;}
	if (!ch[root][0] && !ch[root][1]){ clear(root); root = 0; return;}
	if (!ch[root][0]){
		int oldroot = root;
		root = ch[root][1], f[root] = 0;								
		clear(oldroot);
		return; 
	}else if (!ch[root][1]){
		int oldroot = root;
		root = ch[root][0], f[root] = 0;
		clear(oldroot);
		return; 
	} 
	int fuckson = pre(), oldroot = root;													
	
	splay(fuckson);
	
	ch[root][1] = ch[oldroot][1];
	f[ch[oldroot][1]] = root;
	
	clear(oldroot);
	update(root);
}

int main(){
	
	rd(n);
	short op; int u, cnt = 0, ans = 0;
	insert(214748364);
	insert(-214748364);
	for (int i = 1; i <= n; i ++){
		rd(op); rd(u);
		if (u == 1) u = 1;
		if (cnt == 0) insert(u);
		if (cnt > 0){
			if (op == 0) insert(u);
			else {
				int pree = key[pre()];
				int nexx = key[next()];
//				printf("fuck\n");
				printf("%d : %d  %d\n", op, pre(), next());
				if (abs(pree - u) <= abs(nexx - u)){
					ans += abs(pree - u);
					del(pree);
				}else {
					(ans += abs(nexx - u)) % MO;
					del(nexx);
				}	
			}
		}
		else if (cnt < 0){
			if (op == 1) insert(u);
			else {
				int pree = key[pre()];
				int nexx = key[next()];
//				printf("FUCK\n");
//				printf("%d : %d  %d\n", op, pre(), next());
				if (abs(pree - u) <= abs(nexx - u)){
					(ans += abs(pree - u)) % MO;
					del(pree);
					
				}else {	
					(ans += abs(nexx - u)) % MO;
					del(nexx);
				}			
				
			}
		}
//		printf(" : %d\n", idx);
//		for (int i = 1; i <= idx; i ++){printf("%d\n", key[idx]);}
		cnt = cnt + (op == 0 ? 1 : -1);
	}
	
	printf("%d\n", ans % MO);

	return 0;
}