У Елисея есть массив \(a\), в котором записаны \(n\) целых чисел.
Если массив \(a\) имеет длину строго больше \(1\), то Елисей может применить к нему операцию устранения минимума:
- Сначала Елисей находит в массиве минимальное число \(m\). Если есть несколько одинаковых минимальных элементов, Елисей может выбрать любой из них.
- Затем выбранный минимальный элемент удаляется из массива. После этого из каждого оставшегося элемента вычитается \(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\) строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите единственное целое число — максимально возможный минимум в \(a\), который можно получить несколькими применениями описанной операции к массиву \(a\).
Примечание
В первом наборе входных данных примера изначальная длина массива \(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\).