解题思路
题目中的“乱翘的数组”本质上要求：
- 任意相邻元素不相等；
- 对于每个中间位置，都必须同时严格大于两边，或者严格小于两边。
这等价于整个数组的相邻大小关系必须交替出现，也就是形如：
P4601.第2题-乱翘的数组hard
题目内容
对于给定的长度为 n 的数组 {a1,a2,...,an}，我们定义“翘数”为同时严格大于或小于左右相邻数的数字。形式化的讲，对于第 i(1<i<n) 个整数 ai ，它被称作“翘数”，当且仅当满足 ai−1<ai>ai+1 或 ai−1>ai<ai+1 。
若一个数组中，所有的满足 i∈(1,n) 的数字 ai 均为“翘数”，且任意相邻的两个元素 aj,aj+1(1≤j＜n) 都不相等，则称该数组为“乱翘的数组”。
现在，对于给定的初始数组，计算最少需要从原数组中删除的数字个数，使得剩余数字按原相对顺序拼接成的新数组是一个“乱翘的数组”。
输入描述
第一行输入一个整数 n(3≤n≤2×105) 代表数组中的元素数量。
第二行输入 n 个整数 a1,a2,...,an(−107≤ai≤107) 代表数组元素。
输出描述
在一行上输出一个整数，代表最少需要删除的数字个数。
样例1
输入
7
1 3 1 4 5 2 0
输出
2
说明
其中一种最优的方案是删除数组中的第五、七个数字。
样例2
输入
3
2 2 2
输出
2
