The lonely M is again playing with his array $a_1, a_2, ..., a_n$ (as playing with his array is the only choice), he wants to choose a subsequence of array like $b_1, b_2, ..., b_m$ that $b_1 \ge b_2 \le b_3 \ge b_4 ... \le ( \ge if \ m \equiv 0 \ (mod \ 2) ) b_m$.

What is the maximum length of subsequence that M can choose which satisfies above condition?

Subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. You can erase any elements, not necessarily going successively. The remaining elements preserve their order.

Input

First line contains only $n$, length of array.

Second line contains the array elements $a_1, a_2, ..., a_n$separated by space.

$1 \leq n \leq 3 \times 10^5$

$1 \leq a_i \leq 3 \times 10^5$

Output

The only line of output contains an integer, the maximum length of subsequence that M can choose.