C. Устранение минимума
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Елисея есть массив $$$a$$$, в котором записаны $$$n$$$ целых чисел.

Если массив $$$a$$$ имеет длину строго больше $$$1$$$, то Елисей может применить к нему операцию устранения минимума:

  1. Сначала Елисей находит в массиве минимальное число $$$m$$$. Если есть несколько одинаковых минимальных элементов, Елисей может выбрать любой из них.
  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]$$$.

Поскольку Елисею нравятся большие числа, он хочет, чтобы и в массиве $$$a$$$ числа были как можно больше.

Формально, он хочет добиться того, чтобы минимальное из чисел в массиве $$$a$$$ было максимально возможным (то есть он максимизирует минимум). Для этого он может сколько угодно раз (возможно, ноль) применить к массиву операцию устранения минимума. Обратите внимание, что операцию нельзя применять к массиву длины $$$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$$$, который можно получить несколькими применениями описанной операции к массиву $$$a$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных примера изначальная длина массива $$$n = 1$$$. Поэтому к нему нельзя применять устранение минимума. Таким образом, массив остаётся неизменным и ответ равен $$$a_1 = 10$$$.

Во втором наборе входных данных массив всегда будет состоять только из нулей.

В третьем наборе массив будет принимать состояния $$$[\color{blue}{-1}, 2, 0] \to [3, \color{blue}{1}] \to [\color{blue}{2}]$$$. Минимальные элементы выделены $$$\color{blue}{\text{синим}}$$$ цветом. Максимальный из них равен $$$2$$$.

В четвертом наборе массив будет принимать состояния $$$[2, 10, \color{blue}{1}, 7] \to [\color{blue}{1}, 9, 6] \to [8, \color{blue}{5}] \to [\color{blue}{3}]$$$. Аналогично, максимальный из минимальных элементов равен $$$5$$$.