3855: 波浪数

wave.in/out 
LZX用了两个半小时完成了今天的所有题目，他觉得今天稳稳的能AK所有题，所以他计划给大家明天出一道试题，他想起曾经在DOTA游戏中操刀水人在关键时刻释放了一个波浪技能，扭转了他团队的劣势，反败为胜。为了好好纪念这个技能，他决定让大家帮他一起研究波浪数，波浪数的概念是这样的：对于除首尾位置之外的元素，每一个位置要么比两侧相邻的数字小，要么比两侧相邻的数字大。例如 【1,3,2,5,3,4】 就是一个波浪数组，而 【2,3,4,1,2】 则不是，因为第二个位置 3比左边的数字 2 大，比右边的数字 4 小。 **注意**：根据定义，长度小于等于 2 的数组一定是波浪数组。 现在有一个长度为n数组，每次操作可以将任意一个位置的数字修改成任意一个新数字。小C想要将其变成一个波浪数组，请问最少需要修改几次？ 
【数据范围】 
 对于 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。


【输入输出样例 1 说明】
 可以将数组改为 [1,5,2,4,1,3] 或者 [1,0,2,-1,5,3] 等，都是波浪数组，其中加粗的数字表示被修改的数字。我们可以发现至少修改三个数字才可以将原来的数组变为波浪数组，所以答案为 3。 

输入第一行包含一个正整数n，代表数组长度。 接下来一行包含n个正整数，其中第i个数字表示数组的第 i 个元素 ai

一个整数，最少需要修改的次数

6

1 1 2 2 3 3

3