Codeforces Round 966 (Div. 3) |
---|
Finished |
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:
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.
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:
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$$$.
For each test case, output the answers to the operations of type "?".
351 2 5 905 200000015- 2? 2? 1- 1? 1+ 4+ 2? 2+ 6- 4+ 7? 2? 3? 4? 200000053 4 5 6 89? 5- 5? 5+ 1? 2- 6- 8+ 6? 556 7 8 9 1010? 5- 6? 4- 10+ 5- 8+ 3+ 2- 3+ 10
2 2 1 6 3 8 8 2000001 9 9 9 7 1 1
Name |
---|