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

Вам дана перестановка$$$^\dagger$$$ $$$p$$$ длины $$$n$$$.

За одну операцию вы можете выбрать два индекса $$$1 \le i < j \le n$$$ и поменять местами $$$p_i$$$ и $$$p_j$$$.

Найдите минимальное количество операций, которое необходимо сделать, чтобы в итоговой перестановке была ровно одна инверсия$$$^\ddagger$$$.

$$$^\dagger$$$ Перестановкой называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ тоже не является перестановкой ($$$n=3$$$, но $$$4$$$ присутствует в массиве).

$$$^\ddagger$$$ Количеством инверсий в перестановке $$$p$$$ называется количество пар индексов $$$(i, j)$$$ таких, что $$$1 \le i < j \le n$$$ и $$$p_i > p_j$$$.

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

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

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина перестановки.

Вторая строка каждого набора содержит $$$n$$$ чисел $$$p_1,p_2,\ldots, p_n$$$ ($$$1 \le p_i \le n$$$). Гарантируется, что $$$p$$$ — перестановка.

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

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

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

Пример
Входные данные
4
2
2 1
2
1 2
4
3 4 1 2
4
2 4 3 1
Выходные данные
0
1
3
1
Примечание

В первом наборе входных перестановка уже удовлетворяет условию.

Во втором наборе вы можете выполнить операцию с $$$(i,j)=(1,2)$$$, после этого в перестановке $$$[2,1]$$$ будет ровно одна инверсия.

В третьем наборе нельзя выполнить условие меньше чем за $$$3$$$ операции. А за $$$3$$$ операции можно добиться выполнения условия так: $$$(i,j)$$$ должны равняться $$$(1,3)$$$, $$$(2,4)$$$, $$$(3,4)$$$ в соответствующих операциях. Итоговой перестановкой будет $$$[1, 2, 4, 3]$$$, в ней ровно одна инверсия.

В четвёртом наборе нужно сделать обмен, в котором $$$(i,j)=(2,4)$$$, в результате чего перестановка будет равняться $$$[2,1,3,4]$$$.