#416 block

Statement

Statement language

During a break, Hayoon wants to divide a permutation $P=[P_1,P_2,\cdots,P_N]$ into several Lego blocks.

A permutation of length $N$ is a sequence in which every integer from $1$ to $N$ appears exactly once. Every block must contain at least one consecutive element of the original permutation, and the blocks keep their original left-to-right order.

The division must satisfy all of the following conditions.

Every element belongs to exactly one block.
Elements in the same block occupy consecutive positions in the original permutation.
After sorting the elements inside every block in ascending order and concatenating the blocks from left to right, the resulting sequence is $[1,2,\cdots,N]$ .

For example, if $P=[3,4,2,1,5,7,6]$ , it can be divided into the three blocks $(3,4,2,1)$ , , and .

Find the maximum possible number of blocks satisfying all conditions.

Input

The input is given in the following format.

$N$ $P_1\ P_2\ \cdots\ P_N$

Output

Print the maximum possible number of blocks satisfying all conditions.

Constraints

$1 \leq N \leq 1\ 000\ 000$ .
$1 \leq P_i \leq N$ ().

Subtasks

#	Score	Constraints
1	15	$N \leq 8$ .
2	25	$N \leq 2\ 000$ .
3	60	There are no additional constraints.

Samples

Sample 1

Input

7
3 4 2 1 5 7 6

Output

3

Dividing the permutation into $(3,4,2,1)$ , $(5)$ , and $(7,6)$ satisfies all conditions. No division into four or more blocks is possible, so the answer is .