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

Влад нашёл массив $$$a$$$ из $$$n$$$ чисел и решил его отсортировать в порядке неубывания.

Для этого Влад может применить следующую операцию любое количество раз:

  • Извлечь первый элемент массива и вставить его в конец;
  • Обменивать этот элемент с предыдущим, пока он не станет первым или не станет строго больше предыдущего.

Обратите внимание, что оба действия являются частью операции и за одну операцию вы должны применить оба действия.

Например, если применить операцию к массиву [$$$4, 3, 1, 2, 6, 4$$$], то он будет изменяться следующим образом:

  • [$$$\color{red}{4}, 3, 1, 2, 6, 4$$$];
  • [$$$3, 1, 2, 6, 4, \color{red}{4}$$$];
  • [$$$3, 1, 2, 6, \color{red}{4}, 4$$$];
  • [$$$3, 1, 2, \color{red}{4}, 6, 4$$$].

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

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

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

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

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

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

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

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

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