Won, Tak!

Interview

Time limit1sMemory limit1024 MB

Summary

Given N numbers on a circle, find the fewest cuts between adjacent entries so that every resulting arc reads in ascending order.

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

Problem

Hyunbin loves sequences. Above all, he is thrilled by any sequence sorted in ascending order.

Seonwoo wanted to tease Hyunbin, who loves sequences and math, so he brought over a round table with numbered plates in a circle. The plates are numbered 1 to $N$ clockwise, and plate $i$ has $a_{i}$ written on it. Plate $N$ is followed by plate 1.

Hyunbin reads the numbers clockwise. Because the table is round, the numbers wrap around, so he never sees a sorted state. He plans several Won, Tak! operations. One Won, Tak! means the following.

Cut the connection between two adjacent plates.

If the plate with 1 written on it is plate 1, cutting the connections between plates 3 and 4 and between plates 5 and 1 yields two sorted sequences, $[1, 2, 4],\ \[3, 5]$ .

Hyunbin is out of shape and finds each Won, Tak! tiring, so he wants to minimize the number of Won, Tak! operations needed to get a sorted sequence. A sorted sequence is one that is in ascending order when read clockwise. Given the plates on the table, find the minimum number of Won, Tak! operations Hyunbin needs to obtain the desired sequence.

Input

The first line contains the number of plates $N(3 \le N \le 1\ 000\ 000)$ .

The second line contains $a_{i}$ separated by spaces. $(1 \leq i \leq N; 1 \le a_{i} \le 1\,000\,000)$

Output

Print the minimum number of Won, Tak! operations needed.

Hint

An ascending sequence is one whose numbers get larger toward the end.

Examples2

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