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

---

【问题描述】

　　有 \(N\) 位同学站成一排，体育老师要请其中的 \(N-K\) 位同学出列，使得剩下的K位同学排成体操表演队形。

　　体操表演队形是指这样的一种队形：设 \(K\) 位同学从左到右依次编号为：\(1,2,…,K\)，他们的身高分别为 \(h_1,h_2,…,h_K\)， 则他们的身高满足下面两个条件之一：

　　　　\(1）、h_1≤h_2≤⋯≤h_K\)
　　　　\(2）、h_1≥h_2≥⋯≥h_K\)

　　你的任务是，已知所有 N 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成表演队形。

【输入格式】

　　第一行是一个整数 \(N\)，表示同学的总数。
　　第一行有 \(N\) 个整数，用空格分隔，第 \(i\) 个整数 \(h_i\) 是第 \(i\) 位同学的身高（毫米）。

【输出格式】

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

【输入输出样例1】

　Input

8
1860 1860 1500 2000 1870 1300 1970 2200

　Output

3

【输入输出样例1解释】

　　身高位1500,2000和1300的3位同学出列，剩下的1860 1860 1870 1970 2200构成合法的表演队形。

【输入输出样例2】

　Input

6
1860 1860 1500 2000 1870 1300

　Output

2

【输入输出样例2解释】

　　身高位2000和1870的2位同学出列，剩下的1860 1860 1500 1300构成合法的表演队形。

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤N≤10000\)，\(1000≤h_i≤3000\)。

【来源】

　　Mr.he