Towers

题意翻译

有 $n\ (1\le n\le 5000)$ 座塔排在一条直线上,从左到右每个塔的高度分别为 $h_i\ (1\le h_i\le 10^5)$. 每次操作你可以选择一座塔(假设是第 $i$ 座),用吊车把它吊起来,然后放到与它相邻的一座塔上(可以是第 $i-1$ 座也可以是第 $i+1$ 座),这样,新塔的高度为两座塔的和,完成操作后,塔的总数减少一座。 问最少需要多少次操作可以使得所有的塔从左到右形成一个**非递减**序列。

题目描述

The city of D consists of $ n $ towers, built consecutively on a straight line. The height of the tower that goes $ i $ -th (from left to right) in the sequence equals $ h_{i} $ . The city mayor decided to rebuild the city to make it beautiful. In a beautiful city all towers are are arranged in non-descending order of their height from left to right. The rebuilding consists of performing several (perhaps zero) operations. An operation constitutes using a crane to take any tower and put it altogether on the top of some other neighboring tower. In other words, we can take the tower that stands $ i $ -th and put it on the top of either the $ (i-1) $ -th tower (if it exists), or the $ (i+1) $ -th tower (of it exists). The height of the resulting tower equals the sum of heights of the two towers that were put together. After that the two towers can't be split by any means, but more similar operations can be performed on the resulting tower. Note that after each operation the total number of towers on the straight line decreases by 1. Help the mayor determine the minimum number of operations required to make the city beautiful.

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 1<=n<=5000 $ ) — the number of towers in the city. The next line contains $ n $ space-separated integers: the $ i $ -th number $ h_{i} $ ( $ 1<=h_{i}<=10^{5} $ ) determines the height of the tower that is $ i $ -th (from left to right) in the initial tower sequence.

输出格式


Print a single integer — the minimum number of operations needed to make the city beautiful.

输入输出样例

输入样例 #1

5
8 2 7 3 1

输出样例 #1

3

输入样例 #2

3
5 2 1

输出样例 #2

2