解题思路

题目中的“乱翘的数组”本质上要求：

• 任意相邻元素不相等；
• 对于每个中间位置，都必须同时严格大于两边，或者严格小于两边。

这等价于整个数组的相邻大小关系必须交替出现，也就是形如：

题目内容

对于给定的长度为 $n$ 的数组 {$a_1,a_2,...,a_n$}，我们定义“翘数”为同时严格大于或小于左右相邻数的数字。形式化的讲，对于第 $i(1<i<n)$ 个整数 $a_i$ ，它被称作“翘数”，当且仅当满足 $a_{i-1}<a_i>a_{i+1}$ 或 $a_{i-1}>a_i<a_{i+1}$ 。

若一个数组中，所有的满足 $i∈(1,n)$ 的数字 $a_i$ 均为“翘数”，且任意相邻的两个元素 $a_j,a_{j+1}(1≤j＜n)$ 都不相等，则称该数组为“乱翘的数组”。

现在，对于给定的初始数组，计算最少需要从原数组中删除的数字个数，使得剩余数字按原相对顺序拼接成的新数组是一个“乱翘的数组”。

输入描述

第一行输入一个整数 $n(3≤n≤2×10^5)$ 代表数组中的元素数量。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(-10^7≤a_i≤10^7)$ 代表数组元素。

输出描述

在一行上输出一个整数，代表最少需要删除的数字个数。

样例1

输入

7
1 3 1 4 5 2 0

输出

2

说明

其中一种最优的方案是删除数组中的第五、七个数字。

样例2

输入

3
2 2 2

输出

2