← 返回题目列表

Codeforces · 1197/A

A. DIY木梯

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

让我们将 $$$k$$$ 阶梯表示为以下结构:恰好 $$$k + 2$$$ 木板,其中

- 两块长度至少 $$$k+1$$$ 的木板 — 梯子的底部;
- $$$k$$$ 长度至少 $$$1$$$ 的木板 — 梯子的台阶;

请注意,底板和台阶板都不需要相等。

例如,梯子 $$$1$$$ 和 $$$3$$$ 是正确的 $$$2$$$ 阶梯,梯子 $$$2$$$ 是正确的 $$$1$$$ 阶梯。在第一张图片中,底座的木板长度为 $$$[3, 3]$$$,台阶的长度为 $$$[1]$$$。在第二张图片上,基础长度为 $$$[3, 3]$$$,步骤长度为 $$$[2]$$$。在第三张图片上,基础长度为 $$$[3, 4]$$$,台阶长度为 $$$[2, 3]$$$。

你有 $$$n$$$ 木板。第 $$$i$$$ 块木板的长度为 $$$a_i$$$。你没有锯子,所以你无法切割你拥有的木板。尽管你有锤子和钉子,所以你可以用木板组装临时“梯子”。

问题是:最大数量 $$$k$$$ 是多少,以便您可以选择给定木板的某些子集并使用它们组装 $$$k$$$ 阶梯?

输入

第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 100$$$) — 查询数。查询是独立的。

每个查询由两行组成。第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 你拥有的木板数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — 相应木板的长度。

保证所有查询的 Plank 总数不超过 $$$10^5$$$。

输出

打印 $$$T$$$ 整数 — 每个查询一个。第 $$$i$$$ 个整数是最大数量 $$$k$$$,这样您就可以选择第 $$$i$$$ 查询中给出的木板的某个子集,并使用它们组装一个 $$$k$$$ 阶梯。

如果您无法用给定的一组木板制作甚至 $$$1$$$ 阶梯,请打印 $$$0$$$。

示例

输入 #1

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

输出 #1

2
1
2
0

注意

查询 $$$1-3$$$ 的示例显示在图例部分的图像中。

表达梯子质量的俄罗斯模因: