Flower Arrangement

Dongdong, the gardener, has planted a row of flowers with heights (h_1, h_2, \ldots, h_n). As the flowers grow taller they also become more crowded. Dongdong decides to remove some of the flowers such that the remaining ones (in their original order) have room to grow and form an elegant arrangement.

Formally, after some flowers are removed the remaining heights are (g_1, g_2, \ldots, g_m). Dongdong requires that at least one of the following conditions holds:

Condition A: For all (1 \le i \le \frac{m}{2}) (where both neighbors exist), [ g_{2i} > g_{2i-1} \quad \text{and} \quad g_{2i} > g_{2i+1}, ]

Condition B: For all (1 \le i \le \frac{m}{2}), [ g_{2i} < g_{2i-1} \quad \text{and} \quad g_{2i} < g_{2i+1}. ]

Note that when (m=1) (a single flower), both conditions are considered to be satisfied. For (m>1) a valid arrangement will necessarily have an odd length (so that every even-indexed flower has two neighbors).

Your task is to determine the maximum number of flowers Dongdong can keep in place (i.e. the maximum odd length (m)) such that the remaining subsequence (g_1, g_2, \ldots, g_m) satisfies at least one of the given conditions. Equivalently, you need to find the longest alternating subsequence (with strict inequalities between consecutive chosen elements) of odd length. If the longest alternating subsequence has even length, you can remove the last element to obtain an odd-length valid subsequence.

inputFormat

The first line contains an integer (n) ((1 \le n \le 10^5)), the number of flowers. The second line contains (n) integers (h_1, h_2, \ldots, h_n) representing the heights of the flowers.

outputFormat

Output a single integer: the maximum number of flowers Dongdong can keep such that the remaining arrangement satisfies at least one of the conditions.

sample

5
1 2 1 2 1

5