#include<iostream>//treap #include<cstdlib> #include<cstdio> #include<ctime> #define N 80010 #define Mod 1000000 using namespace std; struct data{ int l,r,v,w,rnd; }node[N]; int n,sz,tmp1,tmp2,root,kind; long long ans; /*inline int read(){ int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }*/ void lrotate(int &k){ int t=node[k].r; node[k].r=node[t].l; node[t].l=k;k=t; } void rrotate(int &k){ int t=node[k].l; node[k].l=node[t].r; node[t].r=k;k=t; } void insert(int &k,int x){ if(!k){ node[k=++sz].rnd=rand(); node[k].v=x;node[k].w=1; return; } if(x==node[k].v)node[k].w++; else if(x<node[k].v){ insert(node[k].l,x); if(node[node[k].l].rnd<node[k].rnd)rrotate(k); } else{ insert(node[k].r,x); if(node[node[k].r].rnd<node[k].rnd)lrotate(k); } } void del(int &k,int x){ if(!k)return; if(node[k].v==x){ if(node[k].w>1)node[k].w--; else if(node[k].l*node[k].r==0)k=node[k].l+node[k].r; else if(node[node[k].l].rnd<node[node[k].r].rnd){rrotate(k);del(k,x);} else{lrotate(k);del(k,x);} } else if(x<node[k].v)del(node[k].l,x); else del(node[k].r,x); } void ask_prev(int k,int x){ if(!k)return; if(x>=node[k].v){tmp1=k;ask_prev(node[k].r,x);} else ask_prev(node[k].l,x); } void ask_next(int k,int x){ if(!k)return; if(x<=node[k].v){tmp2=k;ask_next(node[k].l,x);} else ask_next(node[k].r,x); } int main(){ //freopen("pet.in","r",stdin); //freopen("pet.out","w",stdout); //srand(time(0)); scanf("%d",&n); for(int i=1;i<=n;i++){ int a,b; scanf("%d%d",&a,&b); if(root==0){ kind=a; insert(root,b); } else if(kind^a==0)insert(root,b); else{ tmp1=tmp2=-1; ask_prev(root,b);ask_next(root,b); if(tmp1==-1&&tmp2==-1)continue; if(tmp1==-1){ans+=node[tmp2].v-b;ans%=1000000;del(root,node[tmp2].v);} else if(tmp2==-1){ans+=b-node[tmp1].v;ans%=1000000;del(root,node[tmp1].v);} else if(tmp1!=-1&&tmp2!=-1){ if(b-node[tmp1].v>node[tmp2].v-b) {ans+=node[tmp2].v-b;ans%=1000000;del(root,node[tmp2].v);} else{ans+=b-node[tmp1].v;ans%=1000000;del(root,node[tmp1].v);} } } } printf("%lld",ans); return 0; }