Description

The shen niu are standing in a line solving problems. Each shen niu has an ability value $p_i$. loidc feels uncomfortable that the abilities of nearby gold medalists vary widely, so he decides to humanely merge the shen niu.

loidc wants the ability values to be nondecreasing from left to right. Each time, he may choose one shen niu and merge him into one of his two adjacent shen niu. The ability of the new shen niu after the merge equals the sum of the two participants’ abilities. After each merge, the two participants disappear and are replaced by the merged shen niu. The merged shen niu cannot be split again. Therefore, after each merge, the total number of shen niu decreases by $1$.

loidc wants to know the minimum number of merges needed to achieve his goal.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, where the $i$-th integer is $p_i$.

Output Format

Output a single integer, the minimum number of merges loidc needs.

8
1 9 9 4 1 2 2 9

3

Hint

Constraints:

• For $50\%$ of the testdata, $0 \lt n \le 5000$.
• For $100\%$ of the testdata, $0 \lt n \le 2 \times 10^5$, $0 \lt p_i \le 2147483647$, and the $p_i$ are randomly generated.

Translated by ChatGPT 5