Codeforces Round 842 (Div. 2) |
---|
Закончено |
Вам дана перестановка$$$^\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$$$.
Для каждого набора входных данных выведите одно число — минимальное количество операций, которое необходимо сделать, чтобы в итоговом массиве была ровно одна инверсия. Можно показать, что это всегда возможно.
422 121 243 4 1 242 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]$$$.
Название |
---|