Вам дана перестановка\(^\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\).
Выходные данные
Для каждого набора входных данных выведите одно число — минимальное количество операций, которое необходимо сделать, чтобы в итоговом массиве была ровно одна инверсия. Можно показать, что это всегда возможно.
Примечание
В первом наборе входных перестановка уже удовлетворяет условию.
Во втором наборе вы можете выполнить операцию с \((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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
2 1
2
1 2
4
3 4 1 2
4
2 4 3 1
|
0
1
3
1
|