A. Ограниченная сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$. Целое число $$$k$$$ называется хорошим, если и только если возможно отсортировать $$$a$$$ в неубывающем порядке, выполняя следующую операцию произвольное количество раз (возможно, ноль):

  • Сначала выберите два индекса $$$i$$$ и $$$j$$$ ($$$1 \le i \lt j \le n$$$), такие что $$$|a_i - a_j| \ge k$$$;
  • Затем поменяйте местами $$$a_i$$$ и $$$a_j$$$.

Необходимо определить наибольшее хорошее целое число $$$k$$$. Если такого наибольшего целого числа не существует, выведите $$$-1$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — наибольшее хорошее целое число $$$k$$$.

Если такого наибольшего целого числа не существует, выведите $$$-1$$$ вместо этого.

Пример
Входные данные
5
1
1
5
1 2 3 4 5
3
1 4 2
5
2 1 5 4 3
6
1 1 4 5 1 4
Выходные данные
-1
-1
2
2
3
Примечание

В первом и втором наборах входных данных, независимо от того, насколько велико $$$k$$$, вы всегда можете отсортировать $$$a$$$ в неубывающем порядке, не выполняя никаких операций.

В третьем наборе входных данных наибольшее хорошее $$$k$$$ равно $$$2$$$. Мы можем выбрать $$$i=2$$$ и $$$j=3$$$ в первой операции, так как $$$|a_2-a_3|=|4-2|=2 \ge k$$$, и $$$a$$$ отсортирован в неубывающем порядке. Можно доказать, что не существует хороших целых чисел больше $$$2$$$.