C - Moderation in all things


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

Initially, we have an array of length 11 containing only the number 00. All natural numbers are listed in ascending order in the “reservation list” (the first number in the list is 11). The array undergoes qq operations. The ithi^{th} operation, is one of the following:

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

You are given information about qq 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 ithi^{th} operation is nn, you should find the n2th\lceil \frac n 2 \rceil^{th} element of the array. Note that the indexing of the array starts from 11.

ورودی🔗

The first line contains an integer qq, which represents the number of operations. Each of the next qq lines contains two integers: pip_i, and kik_i.

If ki=+xk_i = +x, operation Insert(pip_i, xx) is executed. If ki=xk_i = -x, operation Remove(pip_i, xx) is executed.

It is guaranteed that all operations are valid, and no impossible operation is performed on the array.

Additionally, at most 2×1092 \times 10^9 numbers are moved from the reservation list into the array.

0pi,ki2×1090 \leq p_i, |k_i| \leq 2 \times 10^9 0q5×1050 \leq q \leq 5 \times 10^5

خروجی🔗

Output qq lines. In the ithi^{th} line, print the middle element of the array after performing the ithi^{th} operation.

مثال🔗

ورودی نمونه ۱🔗

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

خروجی نمونه ۱🔗

1
5
4
6
5
7
9
10
16
22
Plain text