시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 64 MB 16 13 13 81.250%

문제

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, the sweeps can be mixed arbitrarily, i.e. two left-to-right sweeps can be executed one after another, similarly 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 is of 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 utilised for the task.

입력

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

출력

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

예제 입력 1

6
3 2 4 1 5 6

예제 출력 1

2

예제 입력 2

8
8 7 4 1 5 2 3 6

예제 출력 2

3

힌트

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

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