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$$$。