← 返回题目列表

Codeforces · 229/D

D. 塔

中文机器翻译题面 查看原题

D城由n座塔组成,在一条直线上连续建造。序列中第 i 个(从左到右)的塔的高度等于 hi。市长决定重建这座城市,使其变得更加美丽。在一座美丽的城市中,所有塔楼都按照高度从左到右非降序排列。

重建包括执行多个(可能为零)操作。操作包括使用起重机吊起任何塔并将其完全放在其他相邻塔的顶部。换句话说,我们可以将第 i 个塔放在第 (i - 1) 个塔(如果存在)或第 (i + 1) 个塔(存在)的顶部。由此产生的塔的高度等于两个塔放在一起的高度之和。此后,两座塔无法以任何方式拆分,但可以对所得塔执行更多类似的操作。请注意,每次操作后,直线上的塔总数会减少 1。

帮助市长确定使城市美丽所需的最少操作次数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 5000) — 城市中塔楼的数量。下一行包含 n 个空格分隔的整数:第 i 个数字 hi (1 ≤ hi ≤ 105) 确定初始塔序列中第 i 个(从左到右)塔的高度。

输出

打印一个整数 - 让城市变得美丽所需的最少操作数。

示例

输入 #1

5
8 2 7 3 1

输出 #1

3

输入 #2

3
5 2 1

输出 #2

2