学步园

#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;
}