F. Сдвиг и разворот
ограничение по времени на тест
2 с
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. Вы можете выполнять два типа операций с этим массивом:

  • Сдвиг: переместить последний элемент массива на первое место и сдвинуть все остальные элементы вправо, таким образом получится массив $$$a_n, a_1, a_2, \ldots, a_{n-1}$$$.
  • Разворот: перевернуть весь массив, таким образом получится массив $$$a_n, a_{n-1}, \ldots, a_1$$$.

Ваша задача — отсортировать массив в порядке неубывания с использованием минимального количества операций или определить, что это невозможно.

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

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

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

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

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

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

Для каждого набора входных данных выведите число $$$k$$$ — минимальное количество операций, необходимых для сортировки массива. Если невозможно отсортировать массив с помощью этих операций, выведите $$$-1$$$.

Пример
Входные данные
11
5
3 2 1 5 4
5
1 1 2 1 1
4
3 7 10 5
5
1 2 3 4 5
2
5 1
3
3 4 1
5
4 1 3 4 4
3
5 1 1
4
2 5 5 4
5
2 2 1 1 2
2
5 5
Выходные данные
3
2
-1
0
1
1
3
1
2
2
0
Примечание

В первом наборе входных данных примера, чтобы отсортировать массив [$$$3, 2, 1, 5, 4$$$] нужно выполнить $$$3$$$ операции:

  • Сдвиг, чтобы получить массив [$$$4, 3, 2, 1, 5$$$];
  • Сдвиг, чтобы получить массив [$$$5, 4, 3, 2, 1$$$];
  • Разворот, чтобы получить массив [$$$1, 2, 3, 4, 5$$$].

В третьем наборе входных данных примера можно показать, что массив невозможно отсортировать с помощью данных операций.

В седьмом наборе входных данных примера, чтобы отсортировать массив [$$$4, 1, 3, 4, 4$$$] нужно выполнить $$$3$$$ операции:

  • Разворот, чтобы получить массив [$$$4, 4, 3, 1, 4$$$];
  • Сдвиг, чтобы получить массив [$$$4, 4, 4, 3, 1$$$];
  • Разворот, чтобы получить массив [$$$1, 3, 4, 4, 4$$$].