题目描述

题目译自 PA 2022 Runda 1 Ornitolog 2

交替静绳（Motacilla alterna）是静绳属的一种鸟类。它因其独特的鸟鸣而与众不同，这种鸟的鸟鸣中，连续的音高交替地增加和减少。例如，如果我们用整数来表示音高，那么，鸟鸣可以是 $[2, 1, 3]$ 和 $[4, 5, -6, -5]$，但不能是 $[1, 2, 3, 2]$ 或 $[6, 5, 5, 4]$。为了记录这种迷人的生物，鸟类学家 Bytesar 将他的录音笔留在森林中数天。他现在想知道录到的声音是否与静绳的鸟鸣相似。

写一个程序，给定音高序列，确定最少将音高序列中多少个整数改成 $[-10^9, 10^9]$ 区间内的任意整数，才能使得这个序列成为交替静绳鸟鸣的音高序列。

输入格式

第一行一个整数 $n$ ($3 \le n \le 50\,000$)，表示这个音高序列的长度。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($-10^6 \le a_i \le 10^6$)，表示这个音高序列。

输出格式

输出最少要修改多少整数才能使这个序列成为交替静绳鸟鸣的音高序列。

5
4 1 3 3 1

1

4
-1000000 -1000000 -1000000 -1000000

2

数据规模与约定

对于所有数据，保证：

$3 \le n \le 50,000$

$-10^6 \le a_i \le 10^6$