#D. 波浪

    Type: Default 1000ms 256MiB

波浪

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.

[丛雨]定义了一个波浪数组的概念,其定义如下: 对于除首尾位置之外的元素,每一个位置要么比两侧相邻的数字小,要么比两侧相邻的数字大。例如 [1,3,2,5,3,4][1,3,2,5,3,4] 就是一个波浪数组,而 [2,3,4,1,2][2,3,4,1,2] 则不是,因为第二个位置 33 比左边的数字 22 大,比右边的数字 44 小。现在有一个长度为 nn 数组,每次操作可以将任意一个位置的数字修改成任意一个新数字。丛雨想要将其变成一个波浪数组,请问最小的修改次数是几次?

输入格式 (wave.in)

输入第一行包含一个正整数 nn ,代表数组长度。 接下来一行包含 nn 个正整数,表示这个数组。

输出格式 (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

数据范围

对于 10%10\% 的数据,有 1n201 \le n \le 20 。 对于 30%30\% 的数据,有 1n10001 \le n \le 1000 。 对于再 10%10\% 的数据,有 1n1051 \le n \le 10^5 ,且数组元素各不相同。 对于再 10%10\% 的数据,有 1n1051 \le n \le 10^5 ,且数组元素全部相同。 对于 100%100\% 的数据,有 1n105,1ai1091 \le n \le 10^5, 1 \le a_i \le 10^9

0719

Not Attended
Status
Done
Rule
IOI
Problem
4
Start at
2024-7-19 14:00
End at
2024-7-19 17:30
Duration
3.5 hour(s)
Host
Partic.
30