← 返回题目列表

Codeforces · 1607/C

C. 最小提取

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

Yelisey 有一个由 $$$n$$$ 整数组成的数组 $$$a$$$。

如果 $$$a$$$ 的长度严格大于 $$$1$$$,那么 Yelisei 可以对其应用称为最小提取的操作:

1.首先叶丽塞找到数组中最小的数字$$$m$$$。如果有多个相同的最小值,Yelisey 可以选择其中任何一个。
2. 然后从数组中删除所选的最小元素。之后,从每个剩余元素中减去$$$m$$$。

因此,每次操作后,数组的长度都会减少$$$1$$$。

例如,如果 $$$a = [1, 6, -4, -2, -4]$$$,则其中的最小元素为 $$$a_3 = -4$$$,这意味着执行此操作后数组将等于 $$$a=[1 {- (-4)}, 6 {- (-4)}, -2 {- (-4)}, -4 {- (-4)}] = [5, 10, 2, 0]$$$。

由于 Yelisey 喜欢大数字,因此他希望数组 $$$a$$$ 中的数字尽可能大。

正式来说,他想让数组 $$$a$$$ 中的数字的最小值成为可能的最大值(即他想要最大化最小值)。为此,Yelisey 可以根据需要多次(可能为零)对数组应用最小提取操作。请注意,该操作不能应用于长度为 $$$1$$$ 的数组。

帮助他找出对数组进行多次(可能是零)最小提取操作后,数组的最小元素可以具有的最大值。

输入

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

接下来的 $$$2t$$$ 行包含测试用例的描述。

在每个测试用例的描述中,第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的原始长度。描述的第二行列出了 $$$n$$$ 以空格分隔的整数 $$$a_i$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。

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

输出

打印 $$$t$$$ 行,每行都包含相应测试用例的答案。测试用例的答案是一个整数 - $$$a$$$ 中的最大可能最小值,可以通过对其描述的操作进行多次应用来获得。

示例

输入 #1

8
1
10
2
0 0
3
-1 2 0
4
2 10 1 7
2
2 3
5
3 2 -4 -2 0
2
-1 1
1
-2

输出 #1

10
0
2
5
2
2
2
-2

注意

在第一个示例测试用例中,数组 $$$n 的原始长度 = 1$$$。因此不能对其应用最小提取。因此,数组保持不变,答案是$$$a_1 = 10$$$。

在第二组输入数据中,数组将始终仅由零组成。

在第三组中,数组将按如下方式更改:$$$[\color{blue}{-1}, 2, 0] \to [3, \color{blue}{1}] \to [\color{blue}{2}]$$$。最小元素用 $$$\color{blue}{\text{blue}}$$$ 突出显示。最大的是 $$$2$$$。

在第四组中,数组将被修改为 $$$[2, 10, \color{blue}{1}, 7] \to [\color{blue}{1}, 9, 6] \to [8, \color{blue}{5}] \to [\color{blue}{3}]$$$。同样,最小元素的最大值为$$$5$$$。