The gardener has planted a row of flowers, each with its own height. As the flowers grow taller, they become more crowded. The gardener decides to remove some of the flowers, leaving the rest in their original positions, so that the remaining flowers have more space to grow and the resulting arrangement is more distinctive.

Specifically, the heights of the flowers can be viewed as a sequence $h_1, h_2, \dots, h_n$. Suppose that after some flowers are removed, the heights of the remaining flowers are $g_1, g_2, \dots, g_m$. The gardener wants at least one of the following two conditions to be satisfied:

Condition A: For all $i$, $g_{2i} > g_{2i-1}$ and $g_{2i} > g_{2i+1}$. Condition B: For all $i$, $g_{2i} < g_{2i-1}$ and $g_{2i} < g_{2i+1}$.

Note that when $m=1$, both conditions are satisfied; when $m > 1$, at most one can be satisfied.

What is the maximum number of flowers that can be left in their original positions?

Input

The first line contains an integer $n$, representing the initial number of flowers. The second line contains $n$ integers, $h_1, h_2, \dots, h_n$, representing the height of each flower.

Output

Output a single integer $m$, representing the maximum number of flowers that can be left in their original positions.

Examples

Input 1

5
5 3 2 1 2

Output 1

3

Note

There are several ways to keep exactly 3 flowers. For example, keeping the 1st, 4th, and 5th flowers, with heights 5, 1, and 2 respectively, satisfies Condition B.

Constraints

For 20% of the data, $n \le 10$; For 30% of the data, $n \le 25$; For 70% of the data, $n \le 1000$, $0 \le h_i \le 1000$; For 100% of the data, $1 \le n \le 100,000$, $0 \le h_i \le 1,000,000$. All $h_i$ are generated randomly, and the random numbers are uniformly distributed within the interval.