Initially, we have an array of length containing only the number . All natural numbers are listed in ascending order in the “reservation list” (the first number in the list is ). The array undergoes operations. The operation, is one of the following:
You are given information about 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 operation is , you should find the element of the array. Note that the indexing of the array starts from .
The first line contains an integer , which represents the number of operations. Each of the next lines contains two integers: , and .
If , operation Insert(, ) is executed. If , operation Remove(, ) is executed.
It is guaranteed that all operations are valid, and no impossible operation is performed on the array.
Additionally, at most numbers are moved from the reservation list into the array.
Output lines. In the line, print the middle element of the array after performing the operation.