Merging Gods' Abilities

You are given a sequence of gods, each with an ability value (p_i). They are arranged in a row. Loidc wants the abilities (when read from left to right) to be in non‐decreasing order. To achieve that, he can perform merge operations. In each merge operation, you choose two adjacent gods and merge them into one god. The ability value of the new god is the sum of the two original values. Note that after each merge the total number of gods decreases by 1 and the merged god cannot be split again.

Your task is to compute the minimum number of merge operations required so that the final sequence (of merged segments) is non–decreasing. Equivalently, you can view the process as partitioning the original array into contiguous segments, where the sum of each segment becomes the new ability value. The resulting sequence of segment sums must be non–decreasing. The number of merge operations performed is exactly (n - k), where (n) is the length of the initial sequence and (k) is the number of segments in the partition.

Formally, given an array (a_1, a_2, \dots, a_n), determine the maximum number of segments (k) such that there exists a partition (1 = i_1 < i_2 < \dots < i_{k+1} = n+1) with sums (s_j = \sum_{t=i_j}^{i_{j+1}-1} a_t) satisfying (s_1 \le s_2 \le \cdots \le s_k). Output (n - k).

inputFormat

The first line contains an integer (n) (the number of gods). The second line contains (n) space–separated positive integers representing the ability values (a_1, a_2, \dots, a_n).

outputFormat

Output a single integer, the minimum number of merge operations required so that the resulting sequence of ability values is non–decreasing.

sample

3
1 2 3

0