CF1607C 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)