Дальтон — учитель класса, в котором учатся \(n\) учеников, пронумерованных от \(1\) до \(n\). В классе имеется \(n\) стульев, также пронумерованных от \(1\) до \(n\). Изначально студент \(i\) сидит на стуле \(p_i\). Гарантируется, что \(p_1,p_2,\dots, p_n\) — перестановка длины \(n\).
Студент счастлив, если его номер отличается от номера его стула. Чтобы сделать всех студентов счастливыми, Дальтон может многократно проделать следующую операцию: выбрать двух разных студентов и поменять их стулья местами. Какое минимальное количество ходов необходимо для того, чтобы все студенты были счастливы? Можно показать, что при ограничениях этой задачи можно сделать всех студентов счастливыми за конечное число ходов.
Перестановкой длины \(n\) называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\), расположенных в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) встречается в массиве дважды), и \([1,3,4]\) также не является перестановкой (\(n=3\), но в массиве есть \(4\)).
Выходные данные
Для каждого набора входных данных требуется вывести минимально необходимое количество ходов.
Примечание
В первом наборе входных данных оба студента уже счастливы, поэтому Дальтон может сделать \(0\) ходов.
Во втором наборе входных данных Дальтон может поменять местами стулья студентов \(1\) и \(2\), получив массив \([2, 1, 3]\). Затем он может поменять местами стулья студентов \(2\) и \(3\), получив массив \([2, 3, 1]\). В этот момент все студенты довольны, а он выполнил \(2\) хода. Выполнить задачу меньшим числом ходов невозможно.
В третьем наборе входных данных, поменяв местами стулья студентов \(1\) и \(2\), а затем поменяв местами стулья студентов \(4\) и \(5\), Дальтон за \(2\) хода получил массив \([2, 1, 5, 3, 4]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
2 1
3
1 2 3
5
1 2 5 4 3
4
1 2 4 3
10
10 2 1 3 6 5 4 7 9 8
|
0
2
2
1
1
|