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, $"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$.
The first line contains a single integer $q$ ($1 <= q <= 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 <= t_i <= 2$, $0 <= a_i <= 10^6$):
After each query, output a single integer, the maximum possible mex of the multiset you can obtain using the given operations.
## Input
The first line contains a single integer $q$ ($1 <= q <= 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 <= t_i <= 2$, $0 <= a_i <= 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.
[samples]
**Definitions**
Let $ s \in \Sigma^n $ be a string of length $ n $, where $ \Sigma = \{a, b, \dots, z\} $.
For a substring $ s[l..r] $ of length $ m = r - l + 1 $, define the cyclic substring $ s_{l,r} = s[l]s[l+1]\dots s[r] $.
**Cyclic Palindrome Condition**
A string $ w $ of length $ m $ is a *cyclic palindrome* if:
$$
\exists N \in [m, 2m - 1], \quad \forall i \in [1, N], \quad w[(i-1) \bmod m + 1] = w[(N - i) \bmod m + 1]
$$
**Constraints**
1. $ 1 \le n, q \le 2 \times 10^5 $
2. $ s \in \Sigma^n $, all characters are lowercase English letters.
3. For each query $ i $: $ 1 \le l_i \le r_i \le n $
**Objective**
For each query $ (l_i, r_i) $, determine whether the substring $ w = s[l_i..r_i] $ is a cyclic palindrome.
Output "YES" if it is, "NO" otherwise.