题目描述

奶牛们讨厌黑暗。 为了调整牛棚顶的电灯的亮度，$\red{Bessie}$必须建一座干草堆使得她能够爬上去够到灯泡 。

一共有$\red{N}$大包的干草（$\red{1<=N<=100000）}$$\red{(}$从$\red{1}$到$\red{N}$编号$\red{)}$依靠传送带连续的传输进牛棚来。第$\red{i}$包干草有一个 宽度$\red{W_i(1<=w_i<=10000)}$。所有的干草包的厚度和高度都为$\red{1. Bessie}$必须利用所有$\red{N}$包干草来建立起干草堆，并且按照他们进牛棚的顺序摆放。她可以相放多少包 就放 多少包来建立起$\red{tower}$的地基（当然是紧紧的放在一行中）。

接下来他可以放置下一个草包放在之前一级 的上方来建立新的一级。注意：每一级不能比下面的一级宽。她持续的这么放置，直到所有的草包都被安 置完成。她必须按顺序堆放 ，按照草包进入牛棚的顺序。

说得更清楚一些：一旦她将一个草包放在第二级 ，她不能将接下来的草包放在地基上。 $\red{Bessie}$的目标是建立起最高的草包堆。

输入格式

第$\red{1}$行：一个单一的整数$\red{N}$。

第$\red{2...}$$\red{N+1}$行：一个单一的整数:$\red{W_i}$。

输出格式

第一行：一个单一的整数，表示$\red{Bessie}$可以建立的草包堆的最高高度。

样例

输入样例

3
1
2
3

输出样例

2

提示

输出说明：
前两个（宽度为1和2的）放在底层，总宽度为3，在第二层放置宽度为3的。
           +----------+
           |    3     |
           +---+------+
           | 1 |   2  |
           +---+------+