1 #include<cstdio>
2 #include<iostream>
3 using namespace std;
4 int n,size,root,now,t1,t2;
5 const int mod=1000000;
6 long long ans;
7 int tr[80001][2],num[80001],fa[80001];
8
9 void rotate(int x,int &k){
10 int y=fa[x],z=fa[y],l,r;
11 if (tr[y][0]==x)l=0;else l=1; r=l^1;
12 if (y==k) k=x;
13 else{
14 if (tr[z][0]==y) tr[z][0]=x; else tr[z][1]=x;}//判断x是z的左子树还是右子树
15 fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;//l，r根据前面订，有点晕
16 tr[y][l]=tr[x][r]; tr[x][r]=y;
17 }
18
19 void splay(int x,int &k){
20 int y,z;
21 while (x!=k){//如果x不是根节点
22 y=fa[x];z=fa[y];
23 if (y!=k){
24 if ((tr[y][0]==x)^(tr[z][0]==y)) rotate(x,k);//why？
25 else rotate(y,k);
26 }
27 rotate(x,k);
28 }
29 }
30
31 void insert(int &k,int x,int last){
32 if (k==0){
33 size++;k=size;num[k]=x;fa[k]=last; splay(k,root);return;
34 }
35 if (x>=num[k]) insert(tr[k][1],x,k); else insert(tr[k][0],x,k);
36 }
37
38 void small(int &k,int x){
39 if (k==0) return;
40 if (num[k]<=x) {
41 t1=k;
42 small(tr[k][1],x);
43 }
44 else small(tr[k][0],x);
45 }
46
47 void large(int &k,int x){
48 if (k==0) return;
49 if (num[k]>=x){
50 t2=k;
51 large(tr[k][0],x);
52 }
53 else
54 large(tr[k][1],x);
55 }
56
57 void del(int x) {
58 splay(x,root);
59 if (tr[x][0]*tr[x][1]==0) root=tr[x][0]+tr[x][1];
60 else{
61 int k=tr[x][1];
62 while (tr[k][0]) k=tr[k][0];
63 tr[k][0]=tr[x][0]; fa[tr[x][0]]=k;
64 root=tr[x][1];
65 }
66 fa[root]=0;
67 }
68
69 int main(){
70 scanf("%d",&n);
71 int f,x;
72
73 for (int i=1;i<=n;i++){
74 scanf("%d%d",&f,&x);
75 if (!root) {
76 insert(root,x,0);
77 now=f;
78 }
79 else if (now==f) insert(root,x,0);
80 else{
81 t1=t2=-1;
82 small(root,x); large(root,x);
83 if (t1==-1){
84 ans+=num[t2]-x;ans%=mod;
85 del(t2);
86 }
87 else if (t2==-1){
88 ans+=x-num[t1];ans%=mod;del(t1);
89 }
90 else{
91 if ((num[t2]-x)>=(x-num[t1])){
92 ans+=x-num[t1];ans%=mod;del(t1);
93 }
94 else{
95 ans+=num[t2]-x;ans%=mod;del(t2);
96 }
97 }
98
99 }
100
101 }
102 cout<<ans<<endl;
103 }
