D. Абсолютная сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Массив считается отсортированным, если $$$a_1 \le a_2 \le \dots \le a_n$$$.

Вы должны сделать массив $$$a$$$ отсортированным, выполнив следующую операцию ровно один раз:

  • выбрать целое число $$$x$$$, затем для каждого $$$i \in [1, n]$$$ заменить $$$a_i$$$ на $$$|a_i - x|$$$.

Найдите любое значение $$$x$$$, при котором массив станет отсортированным, или скажите, что такого не существует.

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

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

Каждый набор входных данных состоит из двух строк. В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$). Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^8$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите целое число $$$x$$$ ($$$0 \le x \le 10^9$$$), которое сделает массив отсортированным. Можно показать, что если такое целое $$$x$$$ существует, есть хотя бы одно такое целое число между $$$0$$$ и $$$10^9$$$.

Если такого целого числа не существует, выведите $$$-1$$$. Если есть несколько подходящих значений $$$x$$$, выведите любое из них.

Пример
Входные данные
8
5
5 3 3 3 5
4
5 3 4 5
8
1 2 3 4 5 6 7 8
6
10 5 4 3 2 1
3
3 3 1
3
42 43 42
2
100000000 99999999
6
29613295 52036613 75100585 78027446 81409090 73215
Выходные данные
4
-1
0
42
2
-1
100000000
40741153
Примечание

В первом наборе входных данных, если применить $$$x = 4$$$, массив станет $$$[1, 1, 1, 1, 1]$$$.

В третьем наборе входных данных, если применить $$$x = 0$$$, массив станет $$$[1, 2, 3, 4, 5, 6, 7, 8]$$$.

В четвертом наборе входных данных, если применить $$$x = 42$$$, массив станет $$$[32, 37, 38, 39, 40, 41]$$$.