P9771 [HUSTFC 2023] Permutation Sorting Problem

JokerShaco has a permutation $p$ of length $n$. He believes a permutation must be ordered, so he plans to sort it. He can perform the following operations on this permutation: - Cut the permutation into several sequences (or do not cut it and keep it as is). Each sequence must contain at least one element. - Choose some of these sequences and reverse them. - Recombine and concatenate these sequences in any order he wants to obtain a new permutation. JokerShaco thinks the cutting operation is very tiring. He wants to know: if the permutation must be made ordered, what is the minimum number of cuts required. A permutation of length $n$ is defined as a sequence containing $n$ distinct integers from $1$ to $n$, where each integer appears exactly once. The definition of reversing a sequence is: suppose there is a sequence of length $m$, $[a_1,a_2,\dots,a_{m-1},a_m]$. After reversing it, it becomes $[a_m,a_{m-1},\dots,a_2,a_1]$.

The first line contains an integer $n\ (1\le n\le 10^6)$, representing the length of the permutation $p$. The second line contains $n$ integers, where the $i$-th integer is defined as $p_i$. It is guaranteed that the input $p$ is a permutation of length $n$.

Output one integer, representing the minimum number of cuts needed to make the permutation $p$ ordered.

Translated by ChatGPT 5