时间限制：1秒　　内存限制：256M

---

【问题描述】

　　德国世界杯正在如火如荼地进行，但组织者们已经在为闭幕式做紧张的准备，他们准备在闭幕式上排练一个上千人的大型合唱节目，演唱本届世界杯的主题歌曲。节目设计者不想沿用传统的由底到高或者由高到低的合唱队型，而是别出心裁地设计出一种锯齿合唱队形。
　　所谓锯齿合唱队形是指这样的一种队形：设K位合唱队员从左到右依次编号为 \(1,2,…,K\)，他们的身高分别为 \(T_1,T_2,…,T_K\)，则他们的身高满足：\(T_1 < T_2 > T_3 < T_4> T_5 … \) 或者 \(T_1 > T_2 < T_3 > T_4 < T_5 …\) ；用图示形象表示如下：
　　　　
　　现在有 \(N\) 个合唱队员站成一排，每个队员的身高已经给出，请你计算最少需要其中几位队员出列，就可以使得剩下的 \(N-K\) 位队员排成锯齿合唱队形。

【输入格式】

　　第一行是一个整数 \(N\)，表示队员的总数。
　　第二行有 \(N\) 个整数，用空格分隔，第 \(i\) 个整数 \(T_i(130 <= Ti <= 230)\) 是第 \(i\) 位队员的身高（厘米）。

【输出格式】

　　包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【输入输出样例】

　Input

8
186 186 150 200 160 130 197 220

　Output

3

【数据限制】

　　\(2 ≤ N ≤ 30000\)

【来源】

　　Mr.he