让我们将 $$$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$$$ 的示例显示在图例部分的图像中。
表达梯子质量的俄罗斯模因: