← 返回题目列表

Codeforces · 1749/C

C. 数字游戏

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

Alice 和 Bob 正在玩游戏。它们有一个正整数数组 $$$a$$$,大小为 $$$n$$$。

在开始游戏之前,Alice 选择一个整数 $$$k \ge 0$$$。游戏持续$$$k$$$阶段,阶段编号从$$$1$$$到$$$k$$$。在第 $$$i$$$ 阶段,Alice 必须从数组中删除一个小于或等于 $$$k - i + 1$$$ 的元素。之后,如果数组不为空,Bob 必须将 $$$k - i + 1$$$ 添加到数组的任意元素。请注意,爱丽丝的移动和鲍勃的移动都是游戏同一阶段的两个部分。如果 Alice 在某个阶段无法删除某个元素,她就输了。如果第 $$$k$$$ 阶段结束且 Alice 尚未输,则她获胜。

你的任务是确定 $$$k$$$ 的最大值,这样如果两个玩家都发挥最佳,Alice 就可以获胜。鲍勃与爱丽丝比赛,因此如果可能的话,他会尽力让她输掉比赛。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 数组 $$$a$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$)。

输出

对于每个测试用例,打印一个整数 - $$$k$$$ 的最大值,这样如果两个玩家都发挥最佳,Alice 就可以获胜。

示例

输入 #1

4
3
1 1 2
4
4 4 4 4
1
1
5
1 3 2 1 1

输出 #1

2
0
1
3