Printer's Head

Time limit1.5sMemory limit64 MB

Summary

Given a permutation of heights 1..n to print in order, find the minimum number of left-to-right or right-to-left sweeps, where each sweep prints positions in order with heights dropping by 1.

Level: Hard8 of 10
Topics: Greedy, Dynamic programming, Implementation
Solved: No attempts yet

Problem

Johnny bought a 3D printer. He wants to test it on a simple task: print $n$ cuboids with equal square bases and heights $1, 2, \ldots, n$ in the given order. The printer works in left-to-right and right-to-left sweeps, and the sweeps can be mixed arbitrarily, i.e. two left-to-right sweeps can be executed one after another, and similarly for right-to-left. In one sweep the printer can stop over an arbitrary number of fields and print a cuboid on each of them; the first printed cuboid has a given height and each next one is $1$ lower (the head of the printer cools down). The printer cannot print on fields on which something was printed already.

Sweeps cost money. Help Johnny minimise the number of sweeps used for the task.

Input

The first line of the input contains a single positive integer $n$ ( $1 \le n \le 10^6$ ), the number of cuboids to be printed. The second and last line contains a sequence of $n$ pairwise distinct positive integers $a_i$ ( $1 \le a_i \le n$ ). These are the heights of the consecutive cuboids to be printed.

Output

Print a single positive integer: the minimal number of sweeps needed to print the given sequence of cuboids.

Hint

In the first sample, Johnny can print cuboids of heights 6, 5, 4, 3 in one right-to-left sweep, and 2, 1 in a left-to-right sweep.

In the second sample, Johnny can print cuboids of heights 8, 7, 6 in a left-to-right sweep, then 5, 4 in a right-to-left sweep, and finally 3, 2, 1 also in a right-to-left sweep.

Examples2

Example 1
Input
```
6
3 2 4 1 5 6
```
Expected output
```
2
```
Example 2
Input
```
8
8 7 4 1 5 2 3 6
```
Expected output
```
3
```