Дан массив \(a\), состоящий из \(n\) целых чисел. Массив считается отсортированным, если \(a_1 \le a_2 \le \dots \le a_n\).
Вы должны сделать массив \(a\) отсортированным, выполнив следующую операцию ровно один раз:
- выбрать целое число \(x\), затем для каждого \(i \in [1, n]\) заменить \(a_i\) на \(|a_i - x|\).
Найдите любое значение \(x\), при котором массив станет отсортированным, или скажите, что такого не существует.
Выходные данные
Для каждого набора входных данных выведите целое число \(x\) (\(0 \le x \le 10^9\)), которое сделает массив отсортированным. Можно показать, что если такое целое \(x\) существует, есть хотя бы одно такое целое число между \(0\) и \(10^9\).
Если такого целого числа не существует, выведите \(-1\). Если есть несколько подходящих значений \(x\), выведите любое из них.
Примечание
В первом наборе входных данных, если применить \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|