问题 4356 --铁塔2

4356: 铁塔2

时间限制: 2 Sec  内存限制: 256 MB
提交: 4  解决: 3
[提交][状态][讨论版][命题人:]

题目描述

Rainbow 和 Freda 要在 Poetic Island 市的一座山脚下盖房子定居了……盖房子需要钢材,幸运的是,这里有排成一行的n座废弃的铁塔,从左到右编号为1~n,其中第 i 座的高度为h [ i ]。
Rainbow 和 Freda 想盖一座上面小下面大的城堡,并且城堡的层数尽可能多。因此,他们要把这些铁塔分成尽量多组,每组内的铁塔编号必须是连续的,并且从左到右各组内铁塔的高度之和单调不减。但是 Rainbow和 Freda 简直弱爆了有木有,于是请你帮忙计算一下最多能分成多少组呢?

输入

第一行一个整数 n 。
第二行 n 个整数,第 i 个整数表示h [ i ]。

输出

输出一个整数,表示( n − 最多能分成的组数)

样例输入

8
1 9 9 4 1 2 2 9

样例输出

3

提示

0 < n ≤ 200000,0 < h[ i ] ≤ 2147483647

来源

 

[提交][状态]