Minimum Changes to Peak-Valley Sequence

You are given an array of integers. Your task is to determine the minimum number of elements to change in order to transform the array into a peak-valley sequence.

A sequence of n integers a[0], a[1], ..., a[n-1] is called a peak-valley sequence if for every index i where 1 ≤ i ≤ n-2, one of the following conditions holds:

• a[i] < a[i-1] and a[i] < a[i+1] (i.e. a valley), or
• a[i] > a[i-1] and a[i] > a[i+1] (i.e. a peak).

You are allowed to change the value of any element in the array. Find the minimum number of changes required to obtain such a sequence. Note that the first and last elements are not subject to the peak or valley condition.

Formally, you need to find the minimum number k such that by modifying exactly k elements (and leaving the rest unchanged), the array can be transformed into a sequence which satisfies for every index i (with 1 ≤ i ≤ n-2):

\(\text{either } a[i] < a[i-1] \text{ and } a[i] a[i-1] \text{ and } a[i] > a[i+1]\).

inputFormat

The input is read from stdin and has the following format:

1. The first line contains a single integer n (the length of the array).
2. The second line contains n space-separated integers denoting the array elements.

Constraints:

• 1 ≤ n ≤ 10^5
• Each array element is an integer that fits in the machine’s integer range.

outputFormat

Output a single integer to stdout — the minimum number of modifications required to transform the given array into a peak-valley sequence.

## sample

6
4 1 3 2 5 6

0

</p>