Alternating Wagtail

The Motacilla alterna (alternating wagtail) is a bird known for its peculiar song in which the pitch alternates between increasing and decreasing. In other words, if the pitches are represented by integers, a valid song might be [2, 1, 3] or [4, 5, -6, -5], while sequences like [1, 2, 3, 2] or [6, 5, 5, 4] are not valid.

Byteasar, a keen ornithologist, recorded sounds in the forest and now wonders how many changes are needed to turn the recorded sequence of pitches into a valid alternating wagtail song. In one change you may replace any pitch with any integer in the interval \([-10^9, 10^9]\). Determine the minimum number of changes required.

A sequence is considered a valid alternating wagtail song if for every consecutive pair \((a_i,a_{i+1})\) (for \(1 \le i < n\)) the difference \(a_{i+1}-a_i\) is nonzero, and the signs of differences alternate. More formally, for a given alternating pattern, let the desired sign for the difference \(a_i \to a_{i+1}\) be \(+\) or \(-\) according to the pattern. In one possible pattern the first difference is positive, the second is negative, the third is positive, and so on. In the other pattern, the first difference is negative, the second positive, etc. Note that when an element is modified, you can choose any number in \([-10^9, 10^9]\) so that the inequality stated by the pattern is satisfied. However, if an element is not modified, its value is fixed and must satisfy the inequality with its adjacent element.

Your task is to compute the minimum number of modifications needed for making the given sequence a valid alternating wagtail song.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — the length of the pitch sequence.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) (each in the range \([-10^9, 10^9]\)) representing the pitch sequence.

outputFormat

Output a single integer, the minimum number of modifications needed to turn the given sequence into an alternating wagtail song.

sample

3
2 1 3

0