The alternating wagtail (Motacilla alterna) is a bird species from the wagtail family. It is distinguished by a characteristic song in which the pitch of successive sounds alternately rises and falls. For example, if we represent the pitches of sounds as integers, an alternating wagtail might sing $[2, 1, 3]$ and $[4, 5, -6, -5]$, but not $[1, 2, 3, 2]$ or $[6, 5, 5, 4]$. To record these fascinating creatures, the ornithologist Bajtazar left his voice recorder in the forest for a few days. Now he wonders if the recorded sounds are similar to the song of the wagtail.

Write a program that, for a given sequence of sound pitches, determines the minimum number of its elements that need to be changed to a sound of any integer pitch in the range $[-10^9, 10^9]$ so that the sequence represents a possible song of an alternating wagtail.

Input

The first line of standard input contains a single integer $n$ ($3 \le n \le 50\,000$), representing the length of the recording.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-1\,000\,000 \le a_i \le 1\,000\,000$), where $a_i$ is the pitch of the $i$-th sound in the recording.

Output

The output should contain a single integer representing the minimum number of changed sounds.

Examples

Input 1

5
4 1 3 3 1

Output 1

1

Input 2

4
-1000000 -1000000 -1000000 -1000000

Output 2

2

Note

In the first example test, for the sequence to be sung by an alternating wagtail, it is sufficient to change the fourth element of the sequence, for example, to $-1$. In the second example test, at least two elements must be changed, resulting in, for example, the sequence $[-1\,000\,001, -1\,000\,000, -1\,000\,002, -1\,000\,000]$.