Problem Description

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]$.

Input Format

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 Format

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

5
1 2 3 5 4

1

3
3 2 1

0

Hint

Translated by ChatGPT 5