Tower

Byteasar has bought $n$ bricks and numbered them $1$ through $n$. Every brick has the same height, but their widths may differ: brick $i$ has width $w_i$.

He wants to stack all of the bricks into a multi-level tower under the following rules:

• Each level is made of one or more bricks, and the width of a level equals the sum of the widths of the bricks placed on it.
• Going from the bottom level upward, the width of any level must not exceed the width of the level directly beneath it. In other words, the level widths do not increase from bottom to top.
• Bricks must respect their numbering: no brick may sit on a higher level than a brick with a larger identifier. Equivalently, each level is a block of consecutively numbered bricks, and the identifiers only increase as you move up.
• Every brick must be used.

The height of the tower is its number of levels. Find the maximum height Byteasar can build.

The first line contains an integer $n$ ($1 \le n \le 100\,000$), the number of bricks. The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($1 \le w_i \le 10\,000$), where $w_i$ is the width of brick $i$.

Print one integer: the maximum possible height of the tower.

Take the three bricks with widths $1$, $2$, $3$. Put bricks $1$ and $2$ on the bottom level, giving it width $1 + 2 = 3$, and put brick $3$ on the top level, giving it width $3$. Since $3$ does not exceed $3$, this tower is valid and has height $2$.