Problem Description

This problem is translated from PA 2022 Round 1 Ornitolog 2.

The alternate wagtail (Motacilla alterna) is a bird species in the wagtail genus. It is special because of its unique song, in which consecutive pitches alternately increase and decrease. For example, if we use integers to represent pitches, then the song can be $[2, 1, 3]$ and $[4, 5, -6, -5]$, but it cannot be $[1, 2, 3, 2]$ or $[6, 5, 5, 4]$. To record this fascinating creature, the ornithologist Byteasar left his recorder in the forest for several days. He now wants to know whether the recorded sound resembles the wagtail's song.

Write a program that, given a sequence of pitches, determines the minimum number of integers that must be changed to any integers within the range $[-10^9, 10^9]$ in order to make the sequence a valid alternate wagtail song pitch sequence.

Input Format

The first line contains an integer $n$, the length of the pitch sequence.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, representing the pitch sequence.

Output Format

Output the minimum number of integers that need to be modified so that the sequence becomes a valid alternate wagtail song pitch sequence.

5
4 1 3 3 1

1

4
-1000000 -1000000 -1000000 -1000000

2

Hint

For $100\%$ of the testdata, the following constraints hold:

$3 \le n \le 5 \times 10^4$, $-10^6 \le a_i \le 10^6$.

Translated by ChatGPT 5