Патрик любит играть в бейсбол, но иногда он тратит так много часов на пробежки, что его разум начинает затуманиваться! Патрик уверен, что его набранные очки за \(n\) игр соответствуют тождественной перестановке (т.е. в первой игре он набирает \(1\), во второй игре он набирает \(2\) и так далее). Однако, когда он посмотрел на свои записи, он увидел, что все значения перепутаны!
Определим специальный обмен следующим образом: выберите любой подмассив очков и переставьте местами его элементы так, чтобы ни один элемент не оказался в той же позиции, где он был до обмена. Например, выполнение специального обмена на \([1,2,3]\) может дать \([3,1,2]\), но не может дать \([3,2,1]\), так как \(2\) находится в той же позиции.
Вам дана перестановка из \(n\) целых чисел. Пожалуйста, помогите Патрику найти минимальное количество специальных обменов, необходимых для того, чтобы сделать ее отсортированной! Можно доказать, что при данных ограничениях это число не превышает \(10^{18}\).
Массив \(a\) является подмассивом массива \(b\), если \(a\) можно получить из \(b\), удалив несколько (возможно, ноль или все) элементов из начала и несколько (возможно, ноль или все) элементов с конца.
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимальное количество специальных обменов, необходимых для сортировки перестановки.
Примечание
Первая перестановка она уже отсортирована, поэтому обмены не нужны.
Можно показать, что для сортировки второй перестановки нужно как минимум \(2\) обмена.
\([3, 2, 4, 5, 1, 6, 7]\)
Сделаем специальный обмен для диапазона (\(1, 5\))
\([4, 1, 2, 3, 5, 6, 7]\)
Сделаем специальный обмен для диапазона (\(1, 4\))
\([1, 2, 3, 4, 5, 6, 7]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5
1 2 3 4 5
7
3 2 4 5 1 6 7
|
0
2
|