题目描述

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

样例

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

10
0
2
5
2
2
2
-2