#4376. 波浪
波浪
[丛雨]定义了一个波浪数组
的概念,其定义如下:
对于除首尾位置之外的元素,每一个位置要么比两侧相邻的数字小,要么比两侧相邻的数字大。例如 就是一个波浪数组,而 则不是,因为第二个位置 比左边的数字 大,比右边的数字 小。现在有一个长度为 数组,每次操作可以将任意一个位置的数字修改成任意一个新数字。丛雨想要将其变成一个波浪数组,请问最小的修改次数是几次?
输入格式 (wave.in)
输入第一行包含一个正整数 ,代表数组长度。 接下来一行包含 个正整数,表示这个数组。
输出格式 (wave.out)
一行一个整数表示最少修改次数。
输入样例A
6
1 1 2 2 3 3
输出样例A
3
输入样例B
20
1001 1002 1002 1000 1002 1000 1000 1001 1001 1002 1000 1002 1001 1000 1002 1000 1002 1002 1002 1000
输出样例B
6
数据范围
对于 的数据,有 。 对于 的数据,有 。 对于再 的数据,有 ,且数组元素各不相同。 对于再 的数据,有 ,且数组元素全部相同。 对于 的数据,有 。
Related
In following contests: