Minimum Extraction

题意翻译

## 题目描述 *Yelisey* 有一个含有 $n$ 个整数的数组 $a$。 如果 $a$ 的长度大于 $1$，*Yelisey* 就能对它进行一种被称为「提取最小值」的操作： 1. 将最小值 $m$ 从数组中删除，数组的长度会因此缩短 $1$。 （如果有几个相同的 $m$，*Yelisei* 可以凭心情任选一个。） 2. 数组中剩下的元素也会被减去 $m$。 举个例子，有一个数组 $\{1, 6, -4, -2, -4\}$，其中的最小元素是 $-4$。我们将随意删去 $a_3$、$a_5$ 中的一个，再把剩余元素各减去 $-4$。显而易见，操作后的数组长这样：$\{1-(-4),6-(-4),-2-(-4),-4-(-4)\}$，化简后得到答案 $\{5, 10, 2, 0\}$。 由于 Yelisey 更喜欢大数，他希望这种操作能使数组 $a$ 中的元素数值尽可能大。 准确来说，他希望使数组 $a$ 中的最小值最大。为了达到这一目的，*Yelisey* 不惜对数组进行任意次「提取最小值」操作；当然，他也不一定非要进行这种操作。 现在，请你帮助他计算出在进行任意次「提取最小值」操作后，数组 $a$ 中的最小元素可以具有的最大值。 ## 输入输出格式 ### 输入格式 第一行包含一个整数 $t( 1\le t\le10^4 )$，表示询问的次数。 接下来的 $2t$ 行对于每次询问在第一行给出了数组的原始长度 $n(1\le n\le 2⋅10^5)$ 和每个元素的值 $a_i( -10^9\le a_i\le 10^9)$。 ### 输出格式 输出 $t$ 行，每行一个整数表示数次（可以是 $0$ 次）操作后数组 $a$ 中最小数的最大值。 ## 说明/提示 在第一组数据中，数组的原始长度 $n=1$，*Yelisey* 不能对它进行操作。因此最小元素的最大值是 $a_1=10$ 。 在第二组数据中，数组始终只有 $0$。所以，最小元素的最大值为 $a_2=0$。 在第三组数据中，数组的改变过程如下： $\{\color{blue}{-1}$$,2,0\}\to\{ 3,\color{blue}1$$\}\to$ $\{$$\color{blue} {2}$$\}$。所以，最小元素的最大值是 $a_3=2$ 。(当前数组最小的数以蓝色标出） 保证所有询问的数组原始长度 $n$ 之和不超过 $2\cdot 10^5$。 在第四组数据中，数组的改变过程如下：$\{2,10,$$\color{blue}{1}$$,7\}\to\{\color{blue}{1}$$,9,6\}\to\{8,\color {blue}{5}$$\}\to$$\{$$\color{blue}{3}$$\}$。 所以，最小元素的最大值是 $a_4=5$ 。 Translated by @[Aynxul03](https://www.luogu.com.cn/user/267459) & @[li142857](https://www.luogu.com.cn/user/540584)

题目描述

Yelisey has an array $ a $ of $ n $ integers. If $ a $ has length strictly greater than $ 1 $ , then Yelisei can apply an operation called minimum extraction to it: 1. First, Yelisei finds the minimal number $ m $ in the array. If there are several identical minima, Yelisey can choose any of them. 2. Then the selected minimal element is removed from the array. After that, $ m $ is subtracted from each remaining element. Thus, after each operation, the length of the array is reduced by $ 1 $ . For example, if $ a = [1, 6, -4, -2, -4] $ , then the minimum element in it is $ a_3 = -4 $ , which means that after this operation the array will be equal to $ a=[1 {- (-4)}, 6 {- (-4)}, -2 {- (-4)}, -4 {- (-4)}] = [5, 10, 2, 0] $ . Since Yelisey likes big numbers, he wants the numbers in the array $ a $ to be as big as possible. Formally speaking, he wants to make the minimum of the numbers in array $ a $ to be maximal possible (i.e. he want to maximize a minimum). To do this, Yelisey can apply the minimum extraction operation to the array as many times as he wants (possibly, zero). Note that the operation cannot be applied to an array of length $ 1 $ . Help him find what maximal value can the minimal element of the array have after applying several (possibly, zero) minimum extraction operations to the array.

输入输出格式

输入格式

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The next $ 2t $ lines contain descriptions of the test cases. In the description of each test case, the first line contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the original length of the array $ a $ . The second line of the description lists $ n $ space-separated integers $ a_i $ ( $ -10^9 \leq a_i \leq 10^9 $ ) — elements of the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

Print $ t $ lines, each of them containing the answer to the corresponding test case. The answer to the test case is a single integer — the maximal possible minimum in $ a $ , which can be obtained by several applications of the described operation to it.

输入输出样例

输入样例 #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

说明

In the first example test case, the original length of the array $ n = 1 $ . Therefore minimum extraction cannot be applied to it. Thus, the array remains unchanged and the answer is $ a_1 = 10 $ . In the second set of input data, the array will always consist only of zeros. In the third set, the array will be changing as follows: $ [\color{blue}{-1}, 2, 0] \to [3, \color{blue}{1}] \to [\color{blue}{2}] $ . The minimum elements are highlighted with $ \color{blue}{\text{blue}} $ . The maximal one is $ 2 $ . In the fourth set, the array will be modified as $ [2, 10, \color{blue}{1}, 7] \to [\color{blue}{1}, 9, 6] \to [8, \color{blue}{5}] \to [\color{blue}{3}] $ . Similarly, the maximum of the minimum elements is $ 5 $ .