Maximizing Peaks and Valleys in Permutation Split

You are given a permutation p = [p₁, p₂, ..., p_n] of size n (i.e. a sequence containing each integer from 1 to n exactly once). You need to partition this permutation into two non‐empty subsequences q and r (each element must go to exactly one subsequence, and the relative order of elements in each subsequence is the same as in the original permutation).

Define a peak in a sequence as an element (with both a previous and a next element) that is strictly greater than both of its neighbors. That is, if the subsequence is a₁, a₂, ..., a_k, then for any i with 2 ≤ i ≤ k − 1, a_i is a peak if a_i > a_i−1 and a_i > a_i+1.

Similarly, define a valley (or reverse peak) in a sequence as an element (with both neighbors present) that is strictly less than both neighbors. That is, for any i with 2 ≤ i ≤ k − 1, a_i is a valley if a_i < a_i−1 and a_i < a_i+1.

Your goal is to split the permutation into q and r so as to maximize the sum of the number of peaks in q and the number of valleys in r.

Note: The subsequences must be non-empty. The positions for checking peaks or valleys are with respect to the subsequences (i.e. only consecutive elements within the subsequence are considered).

inputFormat

The first line contains an integer n (the size of the permutation). The second line contains n space‐separated integers representing the permutation p₁, p₂, ..., p_n.

outputFormat

Output a single integer — the maximum possible sum of the number of peaks in subsequence q and the number of valleys in subsequence r that can be achieved.

sample

3
1 3 2

0