1 //BOZJ 1208  2 //by Cydiater  3 //2016.9.11  4 #include <iostream>  5 #include <cstdio>  6 #include <cstring>  7 #include <string>  8 #include <algorithm>  9 #include <queue> 10 #include <map> 11 #include <ctime> 12 #include <cmath> 13 #include <iomanip> 14 #include <cstdlib> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n)       for(int i=j;i<=n;i++) 18 #define down(i,j,n)     for(int i=j;i>=n;i--) 19 const int MAXN=1e6+5; 20 const int oo=0x3f3f3f3f; 21 const int mod=1e6; 22 inline int read(){ 23     char ch=getchar();int x=0,f=1; 24     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 25     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 26     return x*f; 27 } 28 int N,tol=0,root=0,ans=0,op,num,maxx,minn,cnt=0; 29 struct Treap{ 30     int leftt,rightt,cnt,siz,v,rnd; 31 }t[MAXN]; 32 namespace solution{ 33     void updata(int k){t[k].siz=t[k].cnt+t[t[k].leftt].siz+t[t[k].rightt].siz;} 34     void lefturn(int &k){ 35         int tt=t[k].rightt;t[k].rightt=t[tt].leftt;t[tt].leftt=k; 36         t[tt].siz=t[k].siz;updata(k);k=tt; 37     } 38     void righturn(int &k){ 39         int tt=t[k].leftt;t[k].leftt=t[tt].rightt;t[tt].rightt=k; 40         t[tt].siz=t[k].siz;updata(k);k=tt; 41     } 42     void insert(int &k,int x){ 43         if(k==0){ 44             k=++tol;t[k].leftt=t[k].rightt=0; 45             t[k].v=x;t[k].cnt=t[k].siz=1;t[k].rnd=rand(); 46             return; 47         } 48         t[k].siz++; 49         if(t[k].v==x){ 50             t[k].cnt++; 51             return; 52         } 53         if(x<t[k].v){ 54             insert(t[k].leftt,x); 55             if(t[t[k].leftt].rnd<t[k].rnd)       righturn(k); 56         }else{ 57             insert(t[k].rightt,x); 58             if(t[t[k].rightt].rnd<t[k].rnd)      lefturn(k); 59         } 60     } 61     void del(int &k,int x){ 62         if(k==0)        return; 63         if(t[k].v==x){ 64             if(t[k].cnt>1){ 65                 t[k].siz--;t[k].cnt--; 66                 return; 67             } 68             if(t[k].leftt*t[k].rightt==0)k=t[k].leftt+t[k].rightt; 69             else if(t[t[k].leftt].rnd<t[t[k].rightt].rnd){ 70                 righturn(k); 71                 del(k,x); 72             }else{ 73                 lefturn(k); 74                 del(k,x); 75             } 76         } 77         else if(x<t[k].v){ 78             t[k].siz--; 79             del(t[k].leftt,x); 80         }else{ 81             t[k].siz--; 82             del(t[k].rightt,x); 83         } 84     } 85     void pre(int k,int x){ 86         if(k==0)        return; 87         if(t[k].v<=x){ 88             minn=k; 89             pre(t[k].rightt,x); 90             return; 91         } 92         if(t[k].v>x)pre(t[k].leftt,x); 93     } 94     void nxt(int k,int x){ 95         if(k==0)        return; 96         if(t[k].v>=x){ 97             maxx=k; 98             nxt(t[k].leftt,x); 99             return;100         }101         if(t[k].v<x)nxt(t[k].rightt,x);102     }103     void slove(){104         N=read();105         while(N--){106             op=read();num=read();107             if(!cnt){108                 if(op){cnt--;insert(root,num);}109                 else  {cnt++;insert(root,num);}110             }else if(cnt>0){111                 if(op){112                     cnt--;maxx=-1;minn=-1;113                     pre(root,num);nxt(root,num);114                     if(maxx==-1&&minn==-1)continue;115                     if(maxx==-1){116                         ans+=num-t[minn].v;117                         ans%=mod;118                         del(root,t[minn].v);119                         continue;120                     }121                     if(minn==-1){122                         ans+=t[maxx].v-num;123                         ans%=mod;124                         del(root,t[maxx].v);125                         continue;126                     }127                     if(num-t[minn].v<=t[maxx].v-num){128                         ans+=num-t[minn].v;129                         ans%=mod;130                         del(root,t[minn].v);131                     }else{132                         ans+=t[maxx].v-num;133                         ans%=mod;134                         del(root,t[maxx].v);135                     }136                 }else{137                     cnt++;138                     insert(root,num);139                 }140             }141             else{142                 if(op){143                     cnt--;144                     insert(root,num);                   145                 }else{146                     cnt++;maxx=-1;minn=-1;147                     pre(root,num);nxt(root,num);148                     if(maxx==-1&&minn==-1)continue;149                     if(maxx==-1){150                         ans+=num-t[minn].v;151                         ans%=mod;152                         del(root,t[minn].v);153                         continue;154                     }155                     if(minn==-1){156                         ans+=t[maxx].v-num;157                         ans%=mod;158                         del(root,t[maxx].v);159                         continue;160                     }161                     if(num-t[minn].v<=t[maxx].v-num){162                         ans+=num-t[minn].v;163                         ans%=mod;164                         del(root,t[minn].v);165                     }else{166                         ans+=t[maxx].v-num;167                         ans%=mod;168                         del(root,t[maxx].v);169                     }170                 }171             }172         }173     }174     void output(){175         cout<<ans<<endl;176     }177 }178 int main(){179     //freopen("input.in","r",stdin);180     using namespace solution;181     slove();182     output();183     return 0;184 }