Problem Description

To adjust the brightness of a lamp, Bessie wants to stack hay bales into a tower, then climb onto the barn roof to replace the light bulb. Hay bales are delivered on a conveyor belt. There will be a total of $n$ bales. The $i$-th bale has width $W_i$, and both its height and length are $1$.

The hay tower must be built starting from the bottom layer. Bessie will take several of the earliest delivered bales and place them on the ground as the first layer, then place the next several bales as the second layer, then build the third layer, and so on. This process repeats until all hay bales are used up.

In each layer, the bales must be placed tightly together with no gaps. Also, for stability, the total width of an upper layer cannot exceed the total width of the layer directly below it. All bales delivered in order must be used; she cannot discard any bale.

Bessie's goal is to build the tallest possible tower. Please help her complete this task.

Input Format

The first line contains an integer $n (1 \le n \le 100000)$.

Lines $2$ to $n + 1$: line $i + 1$ contains an integer $W_i (1 \le W_i \le 10000)$.

Output Format

The first line contains a single integer, representing the maximum height that can be built.

3
1
2
3

2

Hint

Sample Explanation

Put $1$ and $2$ on the first layer, and put $3$ on the second layer.

Translated by ChatGPT 5