该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

丛雨定义了一个“波浪数组”的概念，其定义如下：

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

输入格式

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

接下来一行包含 $n$ 个正整数，表示这个数组。

输出格式

一行一个整数表示最少修改次数。

6
1 1 2 2 3 3

3

20
1001 1002 1002 1000 1002 1000 1000 1001 1001 1002 1000 1002 1001 1000 1002 1000 1002 1002 1002 1000

6

提示

对于 $10\%$ 的数据，有 $1\le n\le 20$。

对于 $30\%$ 的数据，有 $1\le n \le 1000$。

对于再 $10\%$ 的数据，有 $1\le n\le 10^5$，且数组元素各不相同。

对于再 $10\%$ 的数据，有 $1\le n\le 10^5$，且数组元素全部相同。

对于 $100\%$ 的数据，有 $1\le n\le 10^5$，$1\le ai\le 10^9$。