[USACO09OPEN] Tower of Hay G

题目背景

为了调整电灯亮度,贝西要用干草包堆出一座塔,然后爬到牛棚顶去把灯泡换掉。干草包会从传送带上运来,共会出现 $n$ 包干草,第 $i$ 包干草的宽度是 $W_i$,高度和长度统一为 $1$。干草塔要从底层开始铺建。贝西会选择最先送来的若干包干草,堆在地上作为第一层,然后再把紧接着送来的几包干草包放在第二层, 再铺建第三层……重复这个过程,一直到所有的干草全部用完。每层的干草包必须紧靠在一起,不出现缝隙,而且为了建筑稳定,上层干草的宽度不能超过下层的宽度。 按顺序运来的干草包一定要都用上,不能将其中几个干草包弃置不用。贝西的目标是建一座最高的塔,请你来帮助她完成这个任务吧。

题目描述

输入输出格式

输入格式


第一行:一个整数 $n,\ (1 ≤ n ≤ 100000)$ 第二行到 $n + 1$ 行:第 $i + 1$ 行有一个整数 $W_i,\ (1 ≤ W_i ≤ 10000)$。

输出格式


第一行:单个整数,表示可以建立的最高高度。

输入输出样例

输入样例 #1

3
1
2
3

输出样例 #1

2

说明

### 样例解释 将 $1$ 和 $2$ 放在第一层,将 $3$ 放在第二层。