CF229D.Towers

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.

城市 D 由 $n$ 座塔组成，这些塔依次建造在一条直线上。从左到右第 $i$ 座塔的高度为 $h_i$。市长决定重建城市，使其变得“美丽”。在一座美丽的城市中，所有塔的高度必须从左到右构成一个非递减序列。

重建过程包含执行若干次（可能为零次）操作。每次操作使用起重机将任意一座塔整体搬起，并将其叠放在某座相邻塔的顶部。换言之，我们可以将第 $i$ 座塔（从左到右编号）搬起，叠放在第 $i-1$ 座塔（若存在）或第 $i+1$ 座塔（若存在）的顶部。合成后的新塔高度等于被叠放的两座塔高度之和。此后，这两座塔将不可再分离；但可对新形成的塔继续执行类似操作。注意：每次操作后，直线上的塔总数减少 1。

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

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 ≤ 105) determines the height of the tower that is i-th (from left to right) in the initial tower sequence.

第一行包含一个整数 $n$（$1 \leq n \leq 5000$）—— 表示城市中塔的数量。
下一行包含 $n$ 个用空格分隔的整数：其中第 $i$ 个数 $h_i$（$1 \leq h_i \leq 10^5$）表示初始塔序列中从左到右第 $i$ 座塔的高度。

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

输出一个整数——使城市变得美丽所需的最少操作次数。