3666: 波浪(第三轮04)
题目描述
在 DOTA2 第八届国际邀请赛（TI8） 中， 选手 AME 操刀的水人在关键时刻释 放了一个波浪的技能，扭转局势，帮助 OG 战队获得冠军。
为了纪念这一技能，我们引出一个“波浪数组”的概念，其定义如下：
对于除首尾位置之外的元素，每一个位置要么比两侧相邻的数字小，要么比两侧 相邻的数字大。
例如 [1,3,2,5,3,4] 就是一个波浪数组，而 [2,3,4,1,2] 则不是， 因为第二个位置 3 比左边的数字 2 大，比右边的数字 4 小。
**注意**： 根据定义，长度小于等于 2 的数组一定是波浪数组。
现在有一个长度为n数组，你每次操作可以将任意一个位置的数字修改成任意一 个新数字。我们想要将其变成一个波浪数组，请问最小的修改次数是几次？
输入
输入第一行包含一个正整数n，代表数组长度。
接下来一行包含n个正整数，其中第i个数字表示数组的第 i 个元素ai 。
输出
对于每一组询问，输出一行一个整数表示最少修改次数。
样例输入 复制
6
1 1 2 2 3 3样例输出 复制
3提示
【样例 1 输入】
6
1 1 2 2 3 3
【样例 1 输出】
3
【样例 1 说明】
可以将数组改为 [1,5,2,4,1,3] 或者 [1,0,2,-1,5,3] 等，都是波浪数组，其中加粗的 数字表示被修改的数字。我们可以发现至少修改三个数字才可以将原来的数组变 为波浪数组，所以答案为 3。
【样例 2 输入】
11
703 702 703 703 702 703 702 702 702 700 702
【样例 2 输出】
3
【数据范围】
对于 10% 的数据，有 1 ≤ n ≤ 20。
对于 30% 的数据，有 1 ≤ n ≤ 1000。
对于另外 10% 的数据，有 1 ≤ n ≤ 10^5 ，且数组元素各不相同。
对于另外 10% 的数据，有 1 ≤ n ≤ 10^5 ，且数组元素全部相同。
对于 100% 的数据，有 1 ≤ n ≤ 10^5, 1 ≤ ai ≤ 10^9 。