407645: GYM102862 I Strange Mex

I. Strange Mextime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a multiset of integers, which is initially empty. Then you need to process $$$q$$$ queries. With each query, you either add or remove a single integer in the multiset.

After each query you need to calculate the maximum possible mex of the multiset you can obtain, if you can apply the following operations. With a single operation, you can take an element $$$x$$$ that appears at least twice in the multiset, remove one of them and add either $$$x-1$$$ or $$$x+1$$$. These operations do not affect the multiset for the next query.

Mex stands for "minimum excluded": the mex of a multiset of numbers is equal to the smallest non-negative integer which is not present in the multiset. For example, $$$\text{mex}(\{0,1,1,2,4,4\})=3$$$. However, in this problem you can convert this multiset to $$$\{0,1,2,3,4,5\}$$$, in which case mex becomes $$$6$$$.

Input

The first line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^6$$$), the number of queries. The next $$$q$$$ lines describe the queries. The $$$i$$$-th of them contains two integers $$$t_i$$$, $$$a_i$$$ ($$$1 \leq t_i \leq 2$$$, $$$0 \leq a_i \leq 10^6$$$):

• if $$$t_i=1$$$, you need to add $$$a_i$$$ to the multiset;
• if $$$t_i=2$$$, you need to remove one element $$$a_i$$$ from the multiset.

It is guaranteed that for each removal query there will be at least one such integer in the multiset.Output

After each query, output a single integer, the maximum possible mex of the multiset you can obtain using the given operations.

ExampleInput

9
1 0
1 1
1 1
1 2
1 4
1 4
2 1
2 2
1 4

Output

1
2
3
4
5
6
5
2
5