Дан массив $$$a$$$ длины $$$n$$$. Целое число $$$k$$$ называется хорошим, если и только если возможно отсортировать $$$a$$$ в неубывающем порядке, выполняя следующую операцию произвольное количество раз (возможно, ноль):
Необходимо определить наибольшее хорошее целое число $$$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$$$ вместо этого.
51151 2 3 4 531 4 252 1 5 4 361 1 4 5 1 4
-1-1223
В первом и втором наборах входных данных, независимо от того, насколько велико $$$k$$$, вы всегда можете отсортировать $$$a$$$ в неубывающем порядке, не выполняя никаких операций.
В третьем наборе входных данных наибольшее хорошее $$$k$$$ равно $$$2$$$. Мы можем выбрать $$$i=2$$$ и $$$j=3$$$ в первой операции, так как $$$|a_2-a_3|=|4-2|=2 \ge k$$$, и $$$a$$$ отсортирован в неубывающем порядке. Можно доказать, что не существует хороших целых чисел больше $$$2$$$.
| Codeforces Round 1077 (Div. 1) |
|---|
| Закончено |
