测试数据来自 wjszez/2143

【问题描述】
小L又在摆筷子玩了。这次他想把筷子摆出一个漂亮的队形。N根筷子随机摆成一排，底端对齐。他想拿走一些筷子，形成比较别致的队形。
具体而言，筷子的长度可以看成一列整数h1,h2,…,hn。设当一部分筷子被拿走后，剩下的筷子的长度依次为g1,g2,…,gn，则小L希望下面两个条件中至少有一个满足：
条件A：对于所有的1<=i<=m/2，有g2i>g2i-1，同时对于所有的1<=i<=m/2 ，有g2i>g2i+1；
条件B：对于所有的1<=i<=m/2，有g2i<g2i-1，同时对于所有的1<=i<=m/2 ，有g2i<g2i+1。
注意上面两个条件在m=1时同时满足，当m>1时最多有一个能满足。
请问，最多能有多少根筷子可以形成这样别致的队形。

【输入文件】
输入的第一行包含一个整数n，表示开始时筷子的根数。
第二行包含n个整数，依次为h1,h2,…,hn，表示每根筷子的长度。
【输出文件】
输出文件一行，包含一个整数m，表示最多能留在原地的筷子的根数。
【输入样例】
5

5 3 2 1 2
【输出样例】
3
【输入输出样例说明】
有多种方法可以正好保留3根筷子，例如，留下第1、4、5根，长度分别为5、1、2，满足条件B。
数据限制：
对于20%的数据，n≤10；
对于30%的数据，n≤25；
对于70%的数据，n≤1000，0≤hi≤1000；
对于100%的数据，1≤n≤100,000，0≤hi≤1,000,000，所有的hi随机生成，所有随机数服从某区间内的均匀分布。