Патрик любит играть в бейсбол, но иногда он тратит так много часов на пробежки, что его разум начинает затуманиваться! Патрик уверен, что его набранные очки за $$$n$$$ игр соответствуют тождественной перестановке (т.е. в первой игре он набирает $$$1$$$, во второй игре он набирает $$$2$$$ и так далее). Однако, когда он посмотрел на свои записи, он увидел, что все значения перепутаны!

Определим специальный обмен следующим образом: выберите любой подмассив очков и переставьте местами его элементы так, чтобы ни один элемент не оказался в той же позиции, где он был до обмена. Например, выполнение специального обмена на $$$[1,2,3]$$$ может дать $$$[3,1,2]$$$, но не может дать $$$[3,2,1]$$$, так как $$$2$$$ находится в той же позиции.

Вам дана перестановка из $$$n$$$ целых чисел. Пожалуйста, помогите Патрику найти минимальное количество специальных обменов, необходимых для того, чтобы сделать ее отсортированной! Можно доказать, что при данных ограничениях это число не превышает $$$10^{18}$$$.

Массив $$$a$$$ является подмассивом массива $$$b$$$, если $$$a$$$ можно получить из $$$b$$$, удалив несколько (возможно, ноль или все) элементов из начала и несколько (возможно, ноль или все) элементов с конца.