#416 block

Loading problem...

Preparing the statement, recent submissions, and submit form.

#416 block | DOJ

Time limit: 2000 ms
Python time limit: 6000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

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)$ , $(5)$ , and $(7,6)$ .

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$ ( $1 \leq i \leq N$ ).
$P_i \neq P_j$ ( $1 \leq i < j \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

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 $3$ .

Sample 2

Input

10
5 9 8 10 3 4 2 1 6 7

Output

There is no valid division into two or more blocks, so the whole permutation must be one block.

Editorial

View editorial