Today is YQH's birthday, and she received a permutation $a_1, a_2, \dots, a_n$ of length $n$ as a gift, which contains each element from $1, 2, \dots, n$ exactly once.

Since YQH loves ascending order, she intends to sort this permutation so that the final result is in ascending order. However, she discovered a problem: she is not very clever and does not know various $O(n \log n)$ sorting algorithms, so she settled for the $O(n)$ "Stalin Sort".

Stalin Sort is a process defined as follows:

Suppose we want to sort the sequence $a_{1, 2, \dots, n}$. Maintain a stack that is initially empty, and iterate $i$ from $1$ to $n$:

• If $a_i$ is strictly greater than the top of the stack or the stack is empty, push $a_i$ onto the stack.

• Otherwise, $a_i$ is less than or equal to the top of the stack, so do nothing.

Finally, output the elements of the stack from bottom to top as the result.

It is easy to see that this gives us an increasing subsequence of the original permutation, but it might lose too many elements. For example, if we want to sort $[5, 1, 2, 3, 4]$, we only get $[5]$.

Therefore, YQH improved it. Now the sorting process is as follows:

Suppose we want to sort the sequence $a_{1, 2, \dots, n}$. Maintain a stack that is initially empty, and iterate $i$ from $1$ to $n$:

• If $a_i$ is strictly greater than the top of the stack or the stack is empty, push $a_i$ onto the stack.

• Otherwise, $a_i$ is less than or equal to the top of the stack. There are two choices: pop the top of the stack and push $a_i$ onto the stack, or do nothing. Note that you must ensure that at any moment, the elements in the stack are strictly monotonically increasing from bottom to top.

Finally, output the elements of the stack from bottom to top as the result.

For example, if we want to sort $[5, 1, 2, 3, 4]$, the stack changes as $[] \to [5] \to [1] \to [1, 2] \to [1, 2, 3] \to [1, 2, 3, 4]$.

It is easy to see that the final size of the stack depends on the choices made during sorting. YQH naturally wants the final stack to be as large as possible, so she has come to you, hoping you can find the maximum possible size of the final stack for the given permutation.

Input

The first line contains a positive integer $n$, representing the length of the permutation.

The second line contains $n$ distinct integers representing the permutation.

Output

Output a single integer representing the answer.

Examples

Input 1

5
5 1 2 3 4

Output 1

4

Input 2

6
1 6 5 2 3 4

Output 2

4

Note

One possible sequence of stack changes is $[] \to [1] \to [1, 6] \to [1, 5] \to [1, 2] \to [1, 2, 3] \to [1, 2, 3, 4]$.

Input 3

5
4 5 1 2 3

Output 3

2

Note

The only possible sequence of stack changes is $[] \to [4] \to [4, 5] \to [4, 5] \to [4, 5] \to [4, 5]$.

Input 4

(input data)

Output 4

(output data)

Input 5

(input data)

Output 5

(output data)

Constraints

Special Constraint A: There exists a partition of the original sequence $[l_1, r_1], [l_2, r_2], \dots, [l_m, r_m]$, where $l_{i+1} = r_i + 1, l_1 = 1, r_m = n$, such that $\forall j \in [l_i, r_i], a_j = r_i - (j - l_i)$.

Special Constraint B: $a_i$ is guaranteed to be generated randomly.

For all data, it is guaranteed that $1 \le n \le 5 \times 10^5$.