UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3549. [ONTAK2010]Tower

Statistics 下载数据

Description

给定N个积木,编号为1..N,每个积木高度为1,宽度为w_i,你可以把若干个积木放在一层上,堆成若干层,要求满足两个条件:
(1)对于任意一层的积木,他的宽度之和要小于等于他下面那一层的积木(最底层除外)。
(2)不允许编号小的放在编号大的的积木上面。
让你求最多能够堆多少层。

Input


第一行一个数N。
第二行N个整数w_i。

Output

一行一个整数表示答案。

Sample Input

3
1 2 3

Sample Output

2


Hint

【数据范围】

N<=10^5,w_i<=10^4。

Source

By Sbullet