题目描述

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

为了纪念这一技能，我们引出一个“波浪数组”的概念，其定义如下：对于除首尾位置之外的元素，每一个位置要么比两侧相邻的数字小，要么比两侧相邻的数字大。

例如 $[1,3,2,5,3,4]$ 就是一个波浪数组，而 $[2,3,4,1,2]$ 则不是，因为第二个位置 $3$ 比左边的数字 $2$ 大，比右边的数字 $4$ 小。

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

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

输入格式

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

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

输出格式

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

样例 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 \leq n \leq 20$。
• 对于 $30$% 的数据，有 $1 \leq n \leq 1000$。
• 对于另外 $10$% 的数据，有 $1 \leq n \leq 10^5$ ，且数组元素各不相同。
• 对于另外 $10$% 的数据，有 $1 \leq n \leq 10^5$ ，且数组元素全部相同。
• 对于 $100$% 的数据，有 $1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9$。

百度网盘大样例下载 提取码: GFOI

阿里云盘大样例下载

夸克云盘大样例下载