You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

监测站记录到一串长度为 $n$ 的信号强度。工程师希望最终的折线足够"清晰"：除了首尾两个位置外，每个中间位置都必须严格高于左右两个相邻位置，或者严格低于左右两个相邻位置。

换句话说，相邻差值的正负号必须不断交替，且相邻两个数不能相等。

现在你可以进行若干次校准。每次校准可以选择任意一个位置，把它改成任意整数。请问最少需要校准多少个位置，才能让整串信号满足要求？

长度不超过 $2$ 的序列天然满足要求。

输入格式

在文件 zigzagsignal.in 中读入。

第一行输入一个正整数 $n$，表示序列长度。

第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示原始信号强度。

输出格式

在文件 zigzagsignal.out 中输出。

输出一行一个整数，表示最少校准次数。

样例

样例输入 #1

6
1 1 2 2 3 3

样例输出 #1

3

样例输入 #2

11
703 702 703 703 702 703 702 702 702 700 702

样例输出 #2

3

数据范围

• 对于 $10\%$ 的数据，满足 $1 \le n \le 20$。
• 对于 $30\%$ 的数据，满足 $1 \le n \le 1000$。
• 对于另外 $10\%$ 的数据，满足 $1 \le n \le 10^5$，且所有 $a_i$ 两两不同。
• 对于另外 $10\%$ 的数据，满足 $1 \le n \le 10^5$，且所有 $a_i$ 都相同。
• 对于 $100\%$ 的数据，满足 $1 \le n \le 10^5$，$1 \le a_i \le 10^9$。