Problem 25414 --大熊的宠物收养所

25414: 大熊的宠物收养所

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 16  Solved: 11
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][4116kb]

Description

阿狸对爱情充满了幻想……他想为自己喜爱的MM领养一只宠物增进感情。
宠物收养所的老板是阿狸的好朋友大熊。大熊当然愿意帮助阿狸,但需要聪明的阿狸为他解决一些问题。
大熊的收养所提供两种服务:收养被主人遗弃的宠物和让新的主人领养这些宠物。
每个处在收养所的宠物都有一个特点值。同样,每个领养者希望领养的宠物也有一个特点值。
1.如果一个领养者希望领养的宠物的特点值为a,那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。如果存在两只宠物他们的特点值分别为a-b和a+b,那么领养者将会领养特点值为a-b的那只宠物。
2.如果某宠物的特点值为a,存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b,那么特点值为a-b的那个领养者将成功领养该宠物。
一个领养者领养了一个特点值为a的宠物,而它本身希望领养的宠物的特点值为b,那么这个领养者的不满意程度为abs(a-b)。
大熊将一年中领养者和被收养宠物到来收养所的情况给了阿狸,希望阿狸计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时,收养所里面既没有 宠物,也没有领养者。
经过以上三道题你已经明白,阿狸总会把棘手的问题交给你来处理……

Input

第一行为一个正整数n,表示一年当中来到收养所的宠物和领养者的总数。接下来的n行,按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数a, b,其中a=0表示宠物,a=1表示领养者,b表示宠物的特点值或是领养者希望领养宠物的特点值。(同一时间呆在收养所中的,要么全是宠物,要么全是领养者,这些宠物和领养者的个数不会超过10000个)

Output

仅有一个正整数,表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。

Sample Input

5
0 2
0 4
1 3
1 2
1 5

Sample Output

3

HINT


【样例解释】



abs(3-2)
+ abs(2-4)=3,最后一个领养者没有宠物可以领养



【数据范围】



n<=80000

Source

[Submit][Status]