题目描述

最近，阿 Q 开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。

每个领养者都希望领养到自己满意的宠物，阿 Q 根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值 $a$（$a$ 是一个正整数，$a<2^{31}$），而他也给每个处在收养所的宠物一个特点值，这样他就能够很方便的处理整个领养宠物的过程了。

宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少：

• 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为 $a$，那么它将会领养一只目前未被领养的宠物中特点值最接近 $a$ 的一只宠物。任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的。如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为 $a-b$ 和 $a+b$，那么领养者将会领养特点值为 $a-b$ 的那只宠物；
• 收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为 $a$，存在两个领养者他们希望领养宠物的特点值分别为 $a-b$ 和 $a+b$，那么特点值为 $a-b$ 的那个领养者将成功领养该宠物。一个领养者领养了一个特点值为 $a$ 的宠物，而它本身希望领养的宠物的特点值为 $b$，那么这个领养者的不满意程度为 $|a-b|$。

你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。

输入格式

第一行为一个正整数 $n$，表示一年当中来到收养所的宠物和领养者的总数；

接下来的 $n$ 行，按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数 $a,b$，其中 $a=0$ 表示宠物，$a=1$ 表示领养者，$b$ 表示宠物的特点值或是领养者希望领养宠物的特点值。

同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过 $10^4$ 个。

输出格式

仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和，对 $10^6$ 取模以后的结果。

样例

输入样例 1

5
0 2
0 4
1 3
1 2
1 5

输出样例 1

3

样例说明

事件按时间顺序：

1. 宠物，特点值 $2$，收养所全是宠物（宠物数1）。
2. 宠物，特点值 $4$，收养所全是宠物（宠物数2）。
3. 领养者，希望特点值 $3$，收养所全是宠物，选择最接近的宠物：
   • 宠物特点值 $2$：差值 $1$
   • 宠物特点值 $4$：差值 $1$
   • 差值相同，选择较小特点值的宠物，即 $2$。 领养者领养特点值 $2$ 的宠物，不满意程度 $|3-2|=1$，宠物 $2$ 被领养走，收养所还剩宠物 $4$。
4. 领养者，希望特点值 $2$，收养所全是宠物（宠物 $4$），最接近的宠物是 $4$，差值 $2$，领养宠物 $4$，不满意程度 $|2-4|=2$，宠物 $4$ 被领养走，收养所空。
5. 领养者，希望特点值 $5$，收养所空（没有宠物），该领养者无法领养。

总不满意程度：$1+2=3$，输出 $3$。

数据范围

• $1 \le n \le 8 \times 10^4$
• 特点值 $b$ 是正整数且 $b < 2^{31}$
• 同一时刻收养所中宠物或领养者数量不超过 $10^4$

时间限制：1000 ms
内存限制：524288 KB

提示

本题本质是维护两个集合（宠物集合和领养者集合），根据当前收养所的类型（全是宠物或全是领养者）来决定如何匹配。

关键点：

• 收养所同一时刻只能有一种类型（宠物或领养者）。
• 当一个新成员（宠物或领养者）到来时：
  1. 如果收养所为空，则直接加入对应集合。
  2. 如果收养所不为空且类型与当前成员相同，则加入对应集合。
  3. 如果收养所不为空且类型与当前成员不同，则进行匹配：在当前集合中查找与当前成员特点值最接近的元素，若有多个差值相同的，选择特点值较小的那个。计算不满意程度，累加并取模，然后删除匹配的元素。

数据结构： 可以使用平衡树（如 std::set 或手写 Treap/Splay）来维护当前集合，支持插入、删除、查找前驱和后继。

算法步骤：

1. 初始化两个空集合（实际上只需要一个，因为同一时刻只有一种类型），以及一个标记 type 表示当前收养所类型（0 表示宠物，1 表示领养者，-1 表示空）。
2. 初始化总不满意程度 ans = 0。
3. 对于每个事件 (a, b)：
   • 如果当前收养所为空（type == -1），则 type = a，将 b 插入集合。
   • 否则如果 a == type，表示与当前类型相同，插入集合。
   • 否则（a != type），表示需要匹配：
     • 在集合中查找 b 的前驱和后继。
     • 选择差值最小的，若差值相同，选择前驱（即较小值）。
     • 计算差值 d，累加到 ans（ans = (ans + d) % 1000000）。
     • 从集合中删除匹配的元素。
     • 注意：匹配后，如果集合为空，则 type = -1。
4. 输出 ans。

时间复杂度：每个操作 $O(\log m)$，其中 $m$ 是当前集合大小，$m \le 10^4$，对于 $n \le 8\times 10^4$ 可以接受。

注意：使用 set 的 lower_bound 可以找到第一个大于等于 b 的元素（后继），前驱可以通过 prev(it) 获得，但注意边界情况。