Вам дана перестановка $$$p$$$ размера $$$n$$$ (перестановка размера $$$n$$$ — это массив размера $$$n$$$, в котором каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз).
Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
Например, если $$$p = [1, 5, 4, 2, 3]$$$, и мы хотим применить операцию к элементам $$$3$$$ и $$$5$$$, тогда после первого шага операции $$$p = [1, 4, 2]$$$; а после вставки элементов $$$p = [3, 1, 4, 2, 5]$$$.
Ваша задача — определить минимальное количество вышеописанных операций, позволяющих отсортировать перестановку $$$p$$$ в возрастающем порядке (т. е. преобразуйте $$$p$$$ таким образом, что $$$p_1 < p_2 < \dots < p_n$$$).
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — размер перестановки.
Вторая строка набора входных данных содержит $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — заданную перестановку $$$p$$$.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора выходных данных выведите одно целое число — минимальное количество вышеописанных операций, позволяющих отсортировать перестановку $$$p$$$ в возрастающем порядке.
451 5 4 2 331 2 342 1 4 365 2 4 1 6 3
2 0 1 3
В первом примере можно действовать следующим образом:
Название |
---|