C. Moderation in All Things
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Initially, we have an array of length $$$1$$$ containing only the number $$$0$$$. All natural numbers are listed in ascending order in the "reservation list" (the first number in the list is $$$1$$$). The array undergoes $$$q$$$ operations. The $$$i^\mathrm{th}$$$ operation, is one of the following:

  • Insert(p, x): Insert the first $$$x$$$ numbers from the reservation list after the number $$$p$$$ in the array, in ascending order. These numbers are removed from the reservation list.
  • Remove(p, x): Remove the next $$$x$$$ numbers after number $$$p$$$ in the array. These numbers are not returned to the reservation list.

You are given information about $$$q$$$ operations, and you are asked to determine the number written in the middle of the array after each operation. If the length of the array after the $$$i^\mathrm{th}$$$ operation is $$$n$$$, you should find the $$$\lceil\frac{n}{2}\rceil^\mathrm{th}$$$ element of the array. Note that the indexing of the array starts from $$$1$$$.

Input

The first line contains an integer $$$q$$$ ($$$1 \leq q \leq 5\cdot10^5$$$), which represents the number of operations. Each of the next $$$q$$$ lines contains two integers: $$$p_i$$$ ($$$1 \le p_i \le 2\cdot10^9$$$), and $$$k_i$$$ ($$$1 \leq |k_i| \leq 2\cdot10^9$$$).

If $$$k_i = +x$$$, operation Insert($$$p_i$$$, x) is executed. If $$$k_i = -x$$$, operation Remove($$$p_i$$$, x) is executed. It is guaranteed that all operations are valid, and no impossible operation is performed on the array. Additionally, at most $$$2\cdot10^9$$$ numbers are moved from the reservation list into the array.

Output

Output $$$q$$$ lines. In the $$$i^\mathrm{th}$$$ line, print the middle element of the array after performing the $$$i^\mathrm{th}$$$ operation.

Examples
Input
10
0 3
0 2
5 -2
4 1
0 -2
5 2
7 3
3 2
10 5
12 20
Output
1
5
4
6
5
7
9
10
16
22
Input
8
0 1
0 1
1 2
3 2
6 2
3 1
6 2
10 2
Output
0
2
1
3
5
9
5
6