HDD

Interview

Time limit2sMemory limit1024 MB

Summary

Given block numbers in disk rotation order, count the full rotations needed to read blocks 1 through n in sequence.

Level: Easy3 of 10
Topics: Array, Implementation
Solved: No attempts yet

Statement

A hard disk (HDD) stores one large, very important file. The file is split into equal-sized blocks, and the blocks are scattered across the disk instead of lying in order. This is called fragmentation. The file fills the whole disk, but its blocks are not stored consecutively.

A read head can only read data by moving over the disk, and it always moves in the same direction as the disk rotates. Blocks must be read in the order they form the file: first move the head to the first block and read it, then move to the second block and read it, and so on. Because of this, the whole file may not be read in a single rotation.

The head starts in front of the first block. One full rotation is counted each time the head passes from the $n$ -th block back to the first block. Find the minimum number of full rotations the head must make to read the file from the first block to the last block.

Input

The first line contains a positive integer $n$ ( $1 \le n \le 10^5$ ), the number of blocks. The second line contains $n$ distinct integers $p_i$ ( $1 \le p_i \le n$ ) forming a permutation of $1$ to $n$ . $p_i$ is the number of the block stored at the $i$ -th position in the direction of the disk's rotation.

Output

Print one integer: the minimum number of full rotations the head must make to read the whole file from the first block to the last block.

Examples3

Example 1
Input
```
3
3 1 2
```
Expected output
```
1
```
Example 2
Input
```
2
1 2
```
Expected output
```
0
```
Example 3
Input
```
4
4 3 2 1
```
Expected output
```
3
```