#include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int M=2e5+10; const int Mod=1e6; const int INF=0x3f3f3f3f; int n,tot,rt,cnt,ans; struct Node{ int ch[2],val,ff; }t[M]; inline void Rotate(int x){ int y=t[x].ff,z=t[y].ff,k=(x==t[y].ch[1]); t[z].ch[y==t[z].ch[1]]=x; t[x].ff=z; t[y].ch[k]=t[x].ch[k^1]; t[t[x].ch[k^1]].ff=y; t[x].ch[k^1]=y; t[y].ff=x; } void Splay(int x,int aim){ // if(!x) return; while(t[x].ff!=aim){ int y=t[x].ff,z=t[y].ff; if(z!=aim){ if((t[z].ch[0]==y)^(t[y].ch[0]==x)) Rotate(x); else Rotate(y); } Rotate(x); } if(!aim) rt=x; } void Insert(int x){ int u=rt,ff=0; while(u&&t[u].val!=x){ ff=u; u=t[u].ch[t[u].val<x]; } if(!u){ u=++tot; if(ff) t[ff].ch[t[ff].val<x]=u; t[u].ff=ff; t[u].ch[0]=t[u].ch[1]=0; t[u].val=x; } Splay(u,0); } void Find(int x){ int u=rt; if(!u) return ; while(t[u].ch[x>t[u].val]&&x!=t[u].val) u=t[u].ch[x>t[u].val]; Splay(u,0); } int Next(int x,int f){ Find(x); int u=rt; if(t[u].val>=x&&f) return u; if(t[u].val<=x&&!f) return u; u=t[u].ch[f]; while(t[u].ch[f^1]) u=t[u].ch[f^1]; return u; } int Next_Une(int x,int f){ Find(x); int u=rt; if(t[u].val>x&&f) return u; if(t[u].val<x&&!f) return u; u=t[u].ch[f]; while(t[u].ch[f^1]) u=t[u].ch[f^1]; return u; } void Delete(int x){ int lt=Next_Une(x,0); int nt=Next_Une(x,1); Splay(lt,0); Splay(nt,lt); t[nt].ch[0]=0; } int main(){ scanf("%d",&n); Insert(INF); Insert(-INF); while(n--){ int k,x; scanf("%d%d",&k,&x); if(!cnt) Insert(x); if(cnt>0){ if(!k) Insert(x); else{ int a1=t[Next(x,0)].val; int a2=t[Next(x,1)].val; if(abs(a1-x)<=abs(a2-x)){ ans+=abs(a1-x); Delete(a1); } else{ (ans+=abs(a2-x))%=Mod; Delete(a2); } } } if(cnt<0){ if(k) Insert(x); else{ int a1=t[Next_Une(x,0)].val; int a2=t[Next_Une(x,1)].val; if(abs(a1-x)<=abs(a2-x)){ (ans+=abs(a1-x))%=Mod; Delete(a1); } else{ (ans+=abs(a2-x))%=Mod; Delete(a2); } } } cnt=cnt+(k==0?1:-1); } printf("%d\n",ans); return 0; }