Влад нашёл массив \(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\)].
У Влада нет времени проделывать все операции, поэтому он просит вас определить, какое минимальное число операций нужно применить, чтобы отсортировать массив, или сообщить, что это невозможно.
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное число операций, необходимое для сортировки массива. Если это сделать невозможно, в качестве ответа выведите \(-1\).