Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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

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

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

  1. Сначала Елисей находит в массиве минимальное число m. Если есть несколько одинаковых минимальных элементов, Елисей может выбрать любой из них.
  2. Затем выбранный минимальный элемент удаляется из массива. После этого из каждого оставшегося элемента вычитается m.

Таким образом, после каждой операции длина массива уменьшается на 1.

Например, если a=[1,6,−4,−2,−4], то минимальный элемент в нем равен a3=−4, соответственно после этой операции массив станет равен a=[1−(−4),6−(−4),−2−(−4),−4−(−4)]=[5,10,2,0].

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

Формально, он хочет добиться того, чтобы минимальное из чисел в массиве a было максимально возможным (то есть он максимизирует минимум). Для этого он может сколько угодно раз (возможно, ноль) применить к массиву операцию устранения минимума. Обратите внимание, что операцию нельзя применять к массиву длины 1.

Помогите ему найти, какое максимальное значение может иметь минимальный элемент массива после применения к массиву нескольких (возможно, ноль) операций устранений минимума.

Входные данные

В первой строке записано целое число t (1≤t≤104) — количество наборов входных данных.

В следующих 2t строках даны описания наборов входных данных.

В описании каждого набора входных данных первая строка содержит целое число n (1≤n≤2⋅105) — исходная длина массива a. Во второй строке описания через пробел перечислены n целых чисел ai (−109≤ai≤109) — элементы массива a.

Гарантируется, что сумма n по всем наборам входных данных теста не превосходит 2⋅105.

Выходные данные

Выведите 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. Поэтому к нему нельзя применять устранение минимума. Таким образом, массив остаётся неизменным и ответ равен a1=10.

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

В третьем наборе массив будет принимать состояния [−1,2,0]→[3,1]→[2]. Минимальные элементы выделены синим цветом. Максимальный из них равен 2.

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