班级座位（class）
说明
众所周知，蒟蒻队长热衷于给班级的同学们排座位，希望以此来促进同学们的学习这天蒟蒻队长又有了一个新的座位思路——让成绩好的同学和成绩差的同学交叉着坐
是不是就可以让成绩差的同学更好的向成绩好的同学学习，让成绩好的同学更好的帮助成绩差的同学呢？
现在蒟蒻队长已经把前 $n$ 位同学的座位排好了，但是他发现好像座位排的有点问题
于是蒟蒻队长决定重新设定要求，他认为只要对于第 $i$ 位同学来说，要么他左右两侧的同学成绩都比他好，要么左右两侧的同学成绩都比他差，那么就满足蒟蒻队长的要求
当然，这里头尾两位同学不需要满足上述条件
现在蒟蒻队长想知道，如果他有足够多任意成绩的同学，最少需要替换这 $n$ 个同学中的几个人，可以使得这个座位满足蒟蒻队长的要求？
输入格式
输入第一行包含一个整数 $n$ 表示现在的人数输入第二行包含 $n$ 个整数 $a_i$，分别表示每个同学的成绩
| 测试数据 | $n$ | 特殊性质 |
|---|---|---|
| $1$ | $1 \leq n \leq 20$ | 无 |
| $2 \sim 3$ | $1 \leq n \leq 1000$ | 无 |
| $4$ | $1 \leq n \leq 10^5$ | $a_i$均不相同 |
| $5$ | $1 \leq n \leq 10^5$ | $a_i==1$ |
| $6 \sim 10$ | $1 \leq n \leq 10^5$ | 无 |
输出格式
输出最少需要替换几个同学6
1 1 2 2 3 33提示
其中一组方案为：替换 $1$ 号同学为一位成绩为 $2$ 的同学
替换 $4$ 号同学为一位成绩为 $1$ 的同学
替换 $6$ 号同学为一位成绩为 $1$ 的同学
最后 $6$ 位同学的成绩分别为 $2,1,2,1,3,1$ 满足徐老师的要求