← 返回题目列表

Codeforces · 2000/H

H. Ksyusha 和加载组

中文机器翻译题面 查看原题

Ksyusha 决定创办一家游戏开发公司。为了在竞争对手中脱颖而出并取得成功,她决定编写自己的游戏引擎。引擎必须支持最初由 $$$n$$$ 不同整数 $$$a_1、a_2、\ldots、a_n$$$ 组成的集合。

该集合将依次进行 $$$m$$$ 操作。这些操作可以是以下类型:

- 将元素 $$$x$$$ 插入集合中;
- 从集合中删除元素$$$x$$$;
- 报告该组的 $$$k$$$ 负载。

集合的 $$$k$$$-load 被定义为最小正整数 $$$d$$$,使得整数 $$$d, d + 1, \ldots, d + (k - 1)$$$ 不会出现在这个集合中。例如,集合 $$$\{3, 4, 6, 11\}$$$ 的 $$$3$$$ 负载是 $$$7$$$,因为集合中不存在整数 $$$7, 8, 9$$$,并且没有更小的值适合。

Ksyusha 正忙于管理任务,因此您必须编写引擎。为所描述的操作提供有效的支持。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

以下几行描述了测试用例。

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 集合的初始大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 < a_2 < \ldots < a_n \le 2 \cdot 10^6$$$) - 集合的初始状态。

第三行包含一个整数 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — 操作数。

接下来的 $$$m$$$ 行包含操作。操作按以下格式给出:

- + $$$x$$$ ($$$1 \le x \le 2 \cdot 10^6$$$) — 将元素 $$$x$$$ 插入集合中(保证 $$$x$$$ 不在集合中);
- - $$$x$$$ ($$$1 \le x \le 2 \cdot 10^6$$$) — 从集合中删除元素 $$$x$$$(保证 $$$x$$$ 在集合中);
- ? $$$k$$$ ($$$1 \le k \le 2 \cdot 10^6$$$) — 输出集合的 $$$k$$$ 负载的值。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$,$$$m$$$ 也同样如此。

输出

对于每个测试用例,输出“?”类型操作的答案。

示例

输入 #1

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

输出 #1

2 2 1 6 3 8 8 2000001 
9 9 9 7 
1 1