Description

Dongdong the florist planted a row of flowers, each with its own height. As the flowers grow taller, the row becomes crowded. Dongdong decides to remove some of the flowers and leave the rest in place so that the remaining flowers have room to grow. At the same time, he hopes the remaining flowers form a stylish pattern.

Specifically, the heights of Dongdong’s flowers can be seen as a sequence of integers $h_1,h_2,\ldots,h_n$. Suppose that after removing some flowers, the heights of the remaining flowers in order are $g_1,g_2,\ldots,g_m$. Dongdong wants at least one of the following two conditions to hold:

Condition A: For all $1 \le i \le \frac{m}{2}$, $g_{2 i} > g_{2 i - 1}$, and for all $1 \le i \le \frac{m}{2}$, $g_{2 i} > g_{2 i + 1}$;
Condition B: For all $1 \le i \le \frac{m}{2}$, $g_{2 i} < g_{2 i - 1}$, and for all $1 \le i \le \frac{m}{2}$, $g_{2 i} < g_{2 i + 1}$.

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

What is the maximum number of flowers that Dongdong can leave in place?

Input Format

The first line contains an integer $n$, the number of flowers initially.

The second line contains $n$ integers $h_1,h_2,\ldots,h_n$, the heights of the flowers.

Output Format

Output a single line containing an integer, the maximum number of flowers that can be left in place.

5
5 3 2 1 2

3

Hint

Explanation of the sample input and output:

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

Constraints

对于 $20\%$ 的数据，$n \le 10$；
对于 $30\%$ 的数据，$n \le 25$；
对于 $70\%$ 的数据，$n \le 1000$，$0 \le h_i \le 1000$；
对于 $100\%$ 的数据，$1 \le n \le {10}^5$，$0 \le h_i \le {10}^6$，所有的 $h_i$ 随机生成，所有随机数服从某区间内的均匀分布。

Translated by ChatGPT 5