题目描述

DOTA2 第八届国际邀请赛（TI8）中，选手 AME 操刀的水人在关键时刻释放了一个波浪的技能，扭转局势，帮助 OG 战队获得冠军。

为了纪念这一技能，我们引出一个“波浪数组”的概念，其定义如下：

对于除首尾位置之外的元素，每一个位置要么比两侧相邻的数字小，要么比两侧相邻的数字大。

例如 \(\lbrack1,3,2,5,3,4\rbrack\) 就是一个波浪数组，而 \(\lbrack2,3,4,1,2\rbrack\) 则不是，因为第二个位置 \(3\) 比左边的数字 \(2\) 大，比右边的数字 \(4\) 小。

注意：**根据定义，长度小于等于 \(2\) 的数组一定是波浪数组。**

现在有一个长度为 \(n\) 的数组，每次操作可以将任意一个位置的数字修改成任意一个新数字。我们想要将其变成一个波浪数组，请问最小的修改次数是几次？

输入格式

输入第一行包含一个正整数 \(n\)，代表数组长度。

接下来一行包含 \(n\) 个正整数，其中第 \(i\) 个数字表示数组的第 \(i\) 个元素 \(a_i\) 。

输出格式

对于每一组询问，输出一行一个整数表示最少修改次数。

样例 #1

样例输入 #1

6
1 1 2 2 3 3

样例输出 #1

3

样例 #2

样例输入 #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\) ，且数组元素各不相同。

对于另外 \(10\%\) 的数据，有 \(1 \le n \le 10^5\) ，且数组元素全部相同。

对于 \(100\%\) 的数据，有 \(1 \le n \le 10^5, 1 \le a_i \le 10^9\)。