J. The Guards' Challenge - Easy Version
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the easy version, guards can use the operations only once.

In the next round of the Squid Game, players must be arranged by their numbers from $$$1$$$ to $$$n$$$. Guards must rearrange the players that initially are shuffled in a random order. Time is crucial, so they have to minimize the time needed to do that.

A guard can do the following operations :

  • Choose an integer $$$k$$$.
  • Divide the players into $$$k$$$ segments.
  • Shuffle the players while maintaining their relative order. This means that, for example, if the segments contain the players $$$[3,1,5]$$$ and $$$[2,6,4,7]$$$, after shuffling, the players must still appear in that order, meaning that these segments $$$[3,2,6,1,5,4,7]$$$ and $$$[3,1,2,6,5,4,7]$$$ are correct because $$$3,1$$$ and $$$5$$$ appeared in the same order as the segment $$$[3,1,5]$$$ and $$$2,4,6$$$ and $$$7$$$ appeared in the same order as the segment $$$[2,6,4,7]$$$, but $$$[1,2,6,3,5,4]$$$ is not correct because $$$3$$$ appeared after $$$1$$$, not in the same order as $$$[3,1,5]$$$.
Time needed for the operation is equal to $$$k$$$, the number of segments.

The goal of the guards is to rearrange the players into the correct order $$$1,2,...,n$$$, using these operations only once, while minimizing the total time. The guards can perform these operations infinitely, but they must be strategic in choosing the number of segments each time because the more segments they use, the longer it takes.

Input

The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — the number of players.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le n)$$$ — the initial permutation of players.

Output

Print a single integer, the minimum time needed to rearrange the players.

Examples
Input
5
5 4 2 3 1
Output
4
Input
5
3 4 5 1 2
Output
2
Input
6
6 5 4 3 2 1
Output
6
Input
5
1 2 3 4 5
Output
0
Note

In the first test, you can divide the players into $$$4$$$ segments $$$[5]$$$,$$$[4]$$$,$$$[2,3]$$$ and $$$[1]$$$ and shuffle them into $$$[1,2,3,4,5]$$$. So the answer is $$$4$$$.

In the second test, you can divide the players into $$$2$$$ segments $$$[3,4,5]$$$ and $$$[1,2]$$$ and shuffle them into $$$[1,2,3,4,5]$$$. So the answer is $$$2$$$.

In the third test, you can divide the players into $$$6$$$ segments $$$[6]$$$,$$$[5]$$$,$$$[4]$$$,$$$[3]$$$,$$$[2]$$$ and $$$[1]$$$ and shuffle them into $$$[1,2,3,4,5,6]$$$. So the answer is $$$6$$$.