题目描述

阿Q 经营着一家宠物收养所，该收养所提供两种服务：接收被主人遗弃的宠物以及为宠物安排新主人领养。阿Q 为每个领养者计算出其希望领养宠物的特点值 $a$（$a$ 是正整数，且 $a < 2^{31}$），同时也为每只宠物赋予一个特点值。

在收养所运营过程中，存在两种情况：

1. 当被遗弃的宠物数量较多时，若有领养者到来，且其希望领养宠物的特点值为 $a$，则该领养者会领养当前未被领养的宠物中特点值最接近 $a$ 的那一只。任何两只宠物的特点值不同，且不同领养者希望领养宠物的特点值也不相同。若存在两只宠物的特点值分别为 $a - b$ 和 $a + b$ 满足最接近条件，领养者将选择特点值为 $a - b$ 的宠物。
2. 当领养者数量较多时，若有新的被遗弃宠物到来，其特点值为 $a$，则能领养该宠物的是希望领养宠物特点值最接近 $a$ 的领养者。若存在两个领养者希望领养宠物的特点值分别为 $a - b$ 和 $a + b$，特点值为 $a - b$ 的领养者将成功领养该宠物。领养者领养特点值为 $a$ 的宠物，而其希望领养的宠物特点值为 $b$，则该领养者的不满意程度为 $|a - b|$。

已知一年中领养者和被收养宠物来到收养所的情况，要求计算所有成功收养宠物的领养者的不满意程度总和。初始时，收养所内既无宠物也无领养者。

输入格式

1. 第一行输入一个正整数 $n$（$1\leq n\leq 8\times 10^4$），表示一年中来到收养所的宠物和领养者的总数。
2. 接下来的 $n$ 行，按照到来时间先后顺序描述情况。每行包含两个整数 $a, b$，其中 $a = 0$ 代表是宠物，$a = 1$ 代表是领养者，正数 $b$ 表示宠物的特点值或领养者希望领养宠物的特点值。

同时，同一时刻留在收养所内的要么全是宠物，要么全是领养者，且这些宠物和领养者的数量不超过 $10^4$ 个。

输出格式

输出一个正整数，为一年中所有成功收养宠物的领养者的不满意程度总和对 $10^6$ 取模后的结果。

输入输出样例

输入样例

5
0 2
0 4
1 3
1 2
1 5

输出样例

3

样例解释

对于输入样例，分析过程如下：

• 首先来了两只宠物，特点值分别为 2 和 4。
• 接着来了一个领养者，希望领养宠物特点值为 3，此时最接近 3 的宠物特点值是 2，不满意程度为 $|3 - 2| = 1$。
• 然后又来一个领养者，希望领养宠物特点值为 2，最接近 2 的宠物已被领养，下一个接近的是 4，不满意程度为 $|2 - 4| = 2$。
• 最后来的领养者没有可领养的宠物。 所以总的不满意程度为 $|3 - 2| + |2 - 4| = 3$。

数据范围与提示

对于全部数据，$n$ 的范围是 $1\leq n\leq 8\times 10^4$。