Description

初始时，我们有一个长度为 $1$ 的数组，其中仅包含数字 $0$。所有自然数按升序列在“预约列表”中（列表中的第一个数字是 $1$）。该数组将经历 $q$ 次操作。第 $i$ 次操作是以下两种之一：

• Insert$(p, x)$：将预约列表中的前 $x$ 个数字按升序插入到数组中数字 $p$ 之后。这些数字将从预约列表中移除。
• Remove$(p, x)$：删除数组中数字 $p$ 之后的接下来 $x$ 个数字。这些数字不会返回到预约列表。

给定 $q$ 次操作的信息，你需要确定每次操作后数组中间的数字。如果在第 $i$ 次操作后数组的长度为 $n$，则应找到数组的第 $\left\lfloor \frac{n}{2} \right\rfloor$ 个元素。注意数组的索引从 $1$ 开始。

Input Format

第一行包含一个整数 $q$ ($1 \leq q \leq 5 \cdot 10^5$)，表示操作的数量。接下来的 $q$ 行每行包含两个整数：$p_i$ ($1 \leq p_i \leq 2 \cdot 10^9$) 和 $k_i$ ($1 \leq |k_i| \leq 2 \cdot 10^9$)。

如果 $k_i = +x$，则执行操作 Insert$(p_i, x)$。如果 $k_i = -x$，则执行操作 Remove$(p_i, x)$。保证所有操作都是有效的，且不会在数组上执行不可能的操作。此外，最多有 $2 \cdot 10^9$ 个数字从预约列表移入数组。

Output Format

输出 $q$ 行。在第 $i$ 行中，输出执行第 $i$ 次操作后数组的中间元素。

10
0 3
0 2
5 -2
4 1
0 -2
5 2
7 3
3 2
10 5
12 20

1
5
4
6
5
7
9
10
16
22

Hint

翻译由 DeepSeek V3 完成