Ksyusha and the Loaded Set
Contest: Codeforces Round 966 (Div. 3)
Difficulty rating: 2200
Tags: binary search, brute force, data structures, implementation

Ksyusha decided to start a game development company. To stand out among competitors and achieve success, she decided to write her own game engine. The engine must support a set initially consisting of $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$.

The set will undergo $$$m$$$ operations sequentially. The operations can be of the following types:

- Insert element $$$x$$$ into the set;
- Remove element $$$x$$$ from the set;
- Report the $$$k$$$-load of the set.

The $$$k$$$-load of the set is defined as the minimum positive integer $$$d$$$ such that the integers $$$d, d + 1, \ldots, d + (k - 1)$$$ do not appear in this set. For example, the $$$3$$$-load of the set $$$\{3, 4, 6, 11\}$$$ is $$$7$$$, since the integers $$$7, 8, 9$$$ are absent from the set, and no smaller value fits.

Ksyusha is busy with management tasks, so you will have to write the engine. Implement efficient support for the described operations.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The following lines describe the test cases.

The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the initial size of the set.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 < a_2 < \ldots < a_n \le 2 \cdot 10^6$$$) — the initial state of the set.

The third line contains an integer $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the number of operations.

The next $$$m$$$ lines contain the operations. The operations are given in the following format:

- + $$$x$$$ ($$$1 \le x \le 2 \cdot 10^6$$$) — insert element $$$x$$$ into the set (it is guaranteed that $$$x$$$ is not in the set);
- - $$$x$$$ ($$$1 \le x \le 2 \cdot 10^6$$$) — remove element $$$x$$$ from the set (it is guaranteed that $$$x$$$ is in the set);
- ? $$$k$$$ ($$$1 \le k \le 2 \cdot 10^6$$$) — output the value of the $$$k$$$-load of the set.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$, and the same holds for $$$m$$$.

Output format:
For each test case, output the answers to the operations of type "?".

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
3
5
1 2 5 905 2000000
15
- 2
? 2
? 1
- 1
? 1
+ 4
+ 2
? 2
+ 6
- 4
+ 7
? 2
? 3
? 4
? 2000000
5
3 4 5 6 8
9
? 5
- 5
? 5
+ 1
? 2
- 6
- 8
+ 6
? 5
5
6 7 8 9 10
10
? 5
- 6
? 4
- 10
+ 5
- 8
+ 3
+ 2
- 3
+ 10

Example output:
2 2 1 6 3 8 8 2000001 
9 9 9 7 
1 1

Editorial:
We will maintain the elements of a set in std::set. We will also maintain a std::set of free segments (in the form of half-intervals). These segments can be easily updated during insertion and deletion operations. In one case, we need to remove a large segment and insert two small ones; in another case, we need to remove two small ones and insert one large segment. We will find suitable segments using std::set::lower_bound.
To answer the query ?, we will maintain a Cartesian tree, where the keys are pairs (length, left boundary). Additionally, we will store the minimum of all left boundaries at the nodes. Now, to answer the query, it is sufficient to cut the Cartesian tree at $$$k$$$ and take the minimum from the stored minimums.
The time complexity of the solution is: $$$O(n \log n + m \log n)$$$.