← 返回题目列表

Codeforces · 1243/A

A. 最大平方

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

Ujan 决定为房子制作一个新的木制屋顶。他有 $$$n$$$ 矩形木板,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 块木板的大小为 $$$a_i \times 1$$$(即宽度为 $$$1$$$,高度为 $$$a_i$$$)。

现在,Ujan 想要制作一个方形屋顶。他将首先选择一些木板并按某种顺序并排放置。然后他将所有这些木板的垂直边粘在一起。最后,他将从所得形状中切出一个正方形,使正方形的边是水平和垂直的。

例如,如果 Ujan 有长度为 $$$4$$$、$$$3$$$、$$$1$$$、$$$4$$$ 和 $$$5$$$ 的木板,他可以选择长度为 $$$4$$$、$$$3$$$ 和 $$$5$$$ 的木板。然后他可以剪出一个 $$$3 \times 3$$$ 的正方形,这是可能的最大值。请注意,这并不是他获得 $$$3 \times 3$$$ 正方形的唯一方法。

正方形 Ujan 能得到的最大边长是多少?

输入

输入的第一行包含一个整数 $$$k$$$ ($$$1 \leq k \leq 10$$$),即输入中测试用例的数量。

对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 1\,000$$$),即 Ujan 存储的木板数量。下一行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$),木板的长度。

输出

对于每个测试用例,输出一个整数,即正方形的最大可能边长。

示例

输入 #1

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

输出 #1

3
4
1
3

注意

第一个示例对应于语句中的示例。

在第二个示例中,粘合所有 $$$4$$$ 木板将形成 $$$4 \times 4$$$ 正方形。

在第三个示例中,最大可能的正方形是 $$$1 \times 1$$$ 并且可以简单地视为任何木板。