交替鹡鸰（Motacilla alterna）是一种鹡鸰科鸟类。它的特征是其鸣叫声中，连续音调的音高交替上升和下降。例如，如果我们用整数来表示音高，交替鹡鸰可以唱出 $[2, 1, 3]$ 和 $[4, 5, -6, -5]$，但不能唱出 $[1, 2, 3, 2]$ 和 $[6, 5, 5, 4]$。为了记录这些迷人的生物，鸟类学家 Bajtazar 在森林里放置了他的录音机几天。现在他想知道录下的声音是否类似于鹡鸰的鸣叫。

请编写一个程序，对于给定的音高序列，计算最少需要修改多少个音符（将其改为 $[-10^9, 10^9]$ 区间内的任意整数音高），才能使该序列成为一个可能的交替鹡鸰鸣叫序列。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 50\,000$)，表示录音的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-1\,000\,000 \le a_i \le 1\,000\,000$)，其中 $a_i$ 表示录音中第 $i$ 个音符的音高。

输出格式

输出一个整数，表示需要修改的最少音符数量。

样例

输入 1

5
4 1 3 3 1

输出 1

1

输入 2

4
-1000000 -1000000 -1000000 -1000000

输出 2

2

说明

在第一个样例中，为了使序列能被交替鹡鸰唱出，只需修改序列的第四个音符，例如将其改为 $-1$。在第二个样例中，至少需要修改两个音符，例如得到序列 $[-1\,000\,001, -1\,000\,000, -1\,000\,002, -1\,000\,000]$。