D. 植树

内存限制:256 MiB 时间限制:1000 ms 输入文件:tree.in 输出文件:tree.out
题目类型:传统 评测方式:文本比较

题目描述

园丁在园里种了一排高高低低的小树,每棵的高度是h_1, h_2, ..., h_n。过了一段时间,园丁希望剩下小树能够按照一定规律排列,于是决定把其中一部分移走,其余的留在原地。 设剩下的m棵小树高度依次为 g_1,g_2,...,g_m,留下的小树可以按下列规律之一排列: 条件A:对于所有的1≤i≤m/2,满足g_2i > g_2i-1,同时对于所有的1≤i≤ m/2,满足g_2i > g_2i+1; 条件B:对于所有的1≤i≤m/2,满足g_2i < g_2i-1,同时对于所有的1≤i≤ m/2,满足g_2i < g_2i+1。 请问,最多能将多少棵树留在原位。

输入格式

第一行包含一个整数 n,表示开始时小树的数量。
第二行包含n个整数,依次为 h_1 ,h_2 ,…,h_n ,表示每棵树的高度。

输出格式

输出一行,包含一个整数,表示最多能留在原地的小树的数量。

样例

【输入样例】
5
5 3 2 1 2
【输出样例】
3

数据范围与提示

对于20%的数据,n≤10;
对于30%的数据,n≤25;
对于70%的数据,n≤1000;
对于100%的数据,1≤n≤100000,0≤h_i≤1000000。