题目内容

定义一个序列 $b_1, b_2, \dots, b_m$（$m \ge 2$）是“完美波动序列”，当且仅当：

1. 任意相邻元素不相等，即对于 $1 \le j < m$，有 $b_j eq b_{j+1}$；
2. 所有内部元素都是局部极值，即对于 $2 \le i \le m-1$，要么 $b_{i-1} < b_i > b_{i+1}$，要么 $b_{i-1} > b_i < b_{i+1}$。

现在给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$。你可以从中删除任意数量的元素（可以删除零个），但不能改变剩余元素的相对顺序。求最少需要删除多少个元素，才能使剩余序列成为一个完美波动序列。

数据范围：序列长度 $n$ 满足 $3 \le n \le 2 \times 10^5$，每个 $a_i$ 的绝对值不超过 $10^7$。

输入描述

第一行包含一个整数 $n$，表示序列的长度。 第二行包含 $n$ 个整数，表示给定的序列 $a_1, a_2, \dots, a_n$。

输出描述

输出一个整数，表示最少需要删除的元素个数。

样例1

输入

5
1 2 1 2 1

输出

0

说明

给定序列 $[1, 2, 1, 2, 1]$ 已经满足完美波动序列的条件：相邻元素均不相等，且所有内部元素（2、1、2）都是局部极值（分别为极大、极小、极大）。因此不需要删除任何元素，最少删除数量为 0。

样例2

输入

6
1 1 2 3 4 5

输出

4

说明

原序列长度为 6。存在相邻相等元素 1, 1，后面的 2, 3, 4, 5 单调递增，无法形成波动。为了得到完美波动序列，可以保留 $[1, 5]$（删除 1, 2, 3, 4）或者 $[1, 2]$（删除后四个元素），这样长度为 2 且相邻不等，没有内部元素，满足完美波动序列要求。通过题解算法求得最长摆动子序列长度为 2（例如上升-下降模式只能取到首尾），故最少需删除 $6 - 2 = 4$ 个元素。

样例3

输入

4
3 1 4 2

输出

0

说明

序列 $[3, 1, 4, 2]$ 满足：$3 > 1 < 4 > 2$，所有内部元素 1 和 4 均为局部极值，因此它本身就是一个完美波动序列，无需删除，答案为 0。

样例4

输入

3
2 1 2

输出

0

说明

长度为 3，序列 $[2, 1, 2]$ 中 $2 > 1 < 2$，元素 1 为局部极小值，相邻元素均不相等，已经构成完美波动序列，最少删除个数为 0。