← 返回题目列表

Codeforces · 2108/F

F. 倒塌的塔楼

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

Pizano 建造了一个由 $$$n$$$ 塔组成的数组 $$$a$$$,每个塔由 $$$a_i \ge 0$$$ 块组成。

皮萨诺可以推倒一座塔,以便接下来的 $$$a_i$$$ 塔增长 $$$1$$$。换句话说,他可以取出元素$$$a_i$$$,将接下来的$$$a_i$$$元素加一,然后将$$$a_i$$$设置为$$$0$$$。落在塔阵列之外的方块消失了。如果皮萨诺用 $$$0$$$ 方块推倒一座塔,什么也不会发生。

皮萨诺想要以任意顺序推倒所有 $$$n$$$ 塔, 每个恰好一次。也就是说,对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,他将恰好击倒位置 $$$i$$$ 处的塔一次。

此外,所得的塔高度数组 必须是非递减的。这意味着,在他击倒所有$$$n$$$塔后,对于任何$$$i \lt j$$$,位置$$$i$$$的塔不得高于位置$$$j$$$的塔。

您需要输出塔高度结果数组的最大$$$\text{MEX}$$$。

数组的 $$$\text{MEX}$$$ 是数组中不存在的最小非负整数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 塔的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 - 塔的初始高度 $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一个整数 - 最终数组的最大值 $$$\text{MEX}$$$。

示例

输入
复制

8
2
1 2
4
2 1 0 0
10
5 9 3 7 1 5 1 5 4 3
10
1 1 1 1 1 1 1 1 1 1
10
3 2 1 0 3 2 1 0 3 2
5
5 2 0 5 5
1
1000000000
7
4 0 1 0 2 7 7

输出
复制

2
3
7
4
5
4
1
3

注意

第一个测试用例的说明。

第二个测试用例的说明。请注意,所有塔都被击倒一次,并且最终的高度数组是非递减的。