Problem Statement

Vil has a broken chest of drawers at home. Once any drawer of this chest has been pulled out, it cannot be pushed back in, so it becomes impossible to take anything out of the drawer one level below the pulled-out drawer (this does not apply if the pulled-out drawer is the bottom one).

The chest consists of $N$ drawers in total, numbered in order from the bottom, and the $i$-th drawer contains the integer $A_i$ (all $A_i$ are distinct). Consider taking integers out of drawers $B_1,B_2,\dots,B_M$ of this chest in this order and arranging them in the order they were taken out to form a monotonically increasing sequence of length $M$. Here, the following condition must be satisfied.

• For $B$ in the problem statement, there is no $(i,j)(i < j)$ satisfying $B_i-1=B_j$.

Find the length of the longest monotonically increasing sequence satisfying the above condition.

Input

$N$
$A_1\ A_2\ \dots\ A_N$

• All inputs are integers.
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$
• $A_i \neq A_j$ if $i \neq j$

Output

Output the length of the longest monotonically increasing sequence satisfying the condition in the problem statement, followed by a newline.

Sample

5
2 3 4 1 5

4

8
4 3 5 1 7 6 2 8

5

15
12 5 15 3 11 8 14 13 6 10 9 7 4 2 1

8