P2286

#include<bits/stdc++.h>
using namespace std;
const int N=10005,Mod=1000000;
int Q,tot,ans,root,n,fa[N],w[N],s[N][2];

void Rotate(int u){
	int f=fa[u],g=fa[fa[u]],k=s[fa[u]][1]==u;
	s[g][s[g][1]==f]=u,fa[u]=g;
	s[f][k]=s[u][k^1],fa[s[u][k^1]]=f;
	s[u][k^1]=f,fa[f]=u;
}

void splay(int u,int t){
	while(fa[u]!=t){
		int f=fa[u],g=fa[fa[u]];
		if(g!=t){
			printf("CCFCCFCCFCCFCCF\n");//------------这里死循环了
			if((s[f][1]==u)^(s[g][1]==f)) Rotate(u);
			else Rotate(f);
		}
		Rotate(u);
	}
	if(!t) root=u;
}

void Insert(int v){
	int u=root,f=0;
	while(u&&v!=w[u]){f=u;u=s[u][v>w[u]];}
	if(!u){
		u=++tot;
		if(f) s[f][v>w[f]]=u;
		fa[u]=f,w[u]=v;
	}
	splay(u,0);
}

void Find(int v){
	int u=root;
	if(!u) return ;
	while(v!=w[u]&&s[u][v>w[u]]) u=s[u][v>w[u]];
	splay(u,0);
}

int Next(int v,int opt){
	Find(v);
	int u=root;
	if((v>=w[u]&&!opt)||(v<=w[u]&&opt)) return u;
	u=s[u][opt];
	while(s[u][opt^1]) u=s[u][opt^1];
	return u;
}

int _Next(int v,int opt){
	Find(v);
	int u=root;
	if((v>w[u]&&!opt)||(v<w[u]&&opt)) return u;
	u=s[u][opt];
	while(s[u][opt^1]) u=s[u][opt^1];
	return u;
}

void Delete(int v){
	int head=_Next(v,0),tail=_Next(v,1);
	splay(head,0),splay(tail,head);
	s[tail][0]=0;
}

int main(){
	scanf("%d",&Q);
	while(Q--){
		int opt,x;
		scanf("%d%d",&opt,&x);
		if(n==0||(n>0&&opt==0)||(n<0&&opt)) Insert(x);
		else{
			int a=w[Next(x,0)],A=w[Next(x,1)];
			int m=((x-a)<=(A-x)?a:A);
			ans+=abs(m-x);
			ans%=Mod;
			Delete(m);
		}
		if(opt==0) n++;
		else n--;
	}
	printf("%d",ans);
	return 0;
}