Description

Cows so hate the dark. In order to change a lightbulb at the top of the barn, Bessie must build a tower out of bales of hay to climb so that she can reach it. The N (1 <= N <= 100,000) bales of hay (conveniently numbered 1..N) enter the barn sequentially on a conveyor belt. Bale i has integer width $w_i$ (1 <= $w_i$ <= 10,000); all bales have depth and height of one unit.

Bessie must use all N hay bales to build the tower and must lay them down in the order they arrive. She can lay as many bales as she wishes (tightly packed in a line, of course) to create the foundation of the tower. She can then lay some of the next bales on top of the previous level to create the next level (no level can be wider than the level beneath it). She continues this process until all the bales are used. She must stack the bales in the order they arrive, from the bottom to the top of the tower. To be clear: she must not try to sneak a bale back on the foundation after a bale is placed on the second layer.

Bessie's goal is to create the tallest tower possible -- and she already knows how wide each every bale of hay will be as it comes into the barn on the belt. How tall a tower can she construct?

Description

奶牛们不喜欢黑暗。 为了调整牛棚顶的电灯的亮度，Bessie必须建一座干草堆使得她能够爬上去够到灯泡。一共有N大包的干草（1<=N<=100000）(从1到N编号)依靠传送带按顺序传输到牛棚里面。第i包干草有一个宽度$W_i$(1<=$w_i$<=10000)。所有的干草包的厚度和高度都为1.

Bessie必须利用所有N包干草来建立起干草塔，并且按照他们进牛棚的顺序摆放。她可以想放多少包就放多少包以建立起干草塔的地基（当然是紧紧的放在一行中）。接下来他可以把几个接着送进来的草包放在之前一级的上方来建立新的一级。注意：每一级不能比下面的一级宽。她持续的这么放置，直到所有的草包都被安置完成。她必须按照草包进入牛棚的顺序堆放。说得更清楚一些：一旦她将一个草包放在第二级，她不能将接下来的草包放在地基上。

Bessie的目标是建立起最高的干草塔——而且她已经知道每个将会被送进来的草包会是多大。她最高可以建多高的塔呢？

Format

Input

• Line 1: A single integer: N
• Lines 2..N+1: Line i+1 contains a single integer: $w_i$

Output

• Line 1: A single integer, the height of the tallest possible tower that can be built

Samples

3
1
2
3

2

OUTPUT DETAILS:

Use the first bales with width 1 and 2 for the bottom row (total width: 3), then the next bale (width 3) for the top row:

+----------+
|    3     |
+---+------+
| 1 |   2  |
+---+------+