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

输入格式

第一行：单个整数：\(N,1≤N≤100000\)第二行到\(N + 1\)行：第\(i + 1\)行有一个整数\(W_i，1 ≤ W_i ≤ 10000\)

输出格式

第一行：单个整数，表示可以建立的最高高度

样例输入

3
1
2
3

样例输出

2

题解

首先考虑贪心的做法。让我们看下面这张图

如图，一个小学生都明白的道理：对于一个三角形，对它进行等面积变换，为了使其越长，其形状必须越瘦。同理，在这道题中我们可以将干草堆抽象为三角形，为了让干草堆更高，我们只能让其更瘦。这里引用ZKW大佬的证明过程。

任意取出一个能使层数最高的方案，设有\(C_A\)层，把其中从下往上每一层最大的块编号记为\(A_i\)；任取一个能使底边最短的方案，设有\(C_B\)层，把其中从下往上每一层最大的块编号记为\(B_i\)。显然\(A_1>=B_1,A*C_B<=B*C_B\)，这说明至少存在一个k属于(1,\(C_B\))，满足\(A*k-1>=B*k-1且A*k<=B*k\)。也就是说，方案A第K层完全被方案B第K 层包含。构造一个新方案，第K层往上按方案 A，往下按方案B，两边都不要的块放中间当第K层。新方案的层数与A相同，而底边长度与B相同。证毕。

这时我们选择枚举最底层的组成，设\(f[i]\)表示从\(n到i\)中最底层的宽度，则可知\(f[i]=min(sum[j-1到i])\)。由于上一层的宽度永远小于下一层的宽度，所以\(f[j]<=sum[j-1到i]\)

再观察一下，由于所有的干草堆要全部使用且对于第\(i-1\)个干草堆放在第\(h\)层时，第\(i\)个必然放在第\(h\)层或第\(h+1\)层，我们可以令\(sum[i]\)表示宽度的前缀和，而\(sum[i]\)是随i的增大而增大的，所以从\(i到n\)一旦发现一个符合条件的决策\(j\)，便将其取出来更新\(f[i]\)。但是因为这样做的复杂度较大，仍不能通过所有数据。

再次分析，发现所有的决策的值（例如对于决策\(j\)值即为\(sum[j-1])由n\)往前都是单调递减的，也就是一个比一个优。因此决定性的因素则是他们的生效时间。

#include <bits/stdc++.h>
#define maxn 100009
using namespace std;
inline char get(){
    static char buf[3000],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,3000,stdin),p1==p2)?EOF:*p1++; 
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
int num[maxn],dp[maxn],f[maxn],sum[maxn],w[maxn];
int n;
int main(){
    //freopen("1.txt","r",stdin);
    n=read();
    for(register int i=1;i<=n;i++){
        w[i]=read();
        sum[i]=sum[i-1]+w[i];
    }
    num[1]=n+1;
    int h=1,t=1;
    for(register int i=n;i;i--){
        while(h<t && f[num[h+1]]<=sum[num[h+1]-1]-sum[i-1]) ++h;
        f[i]=sum[num[h]-1]-sum[i-1];
        dp[i]=dp[num[h]]+1; 
        num[++t]=i;
        while((t>h) && (f[num[t-1]]-sum[num[t-1]-1]+sum[num[t]-1]>f[num[t]]))t--,num[t]=num[t+1];
    }
    cout<<dp[1];
    return 0;
}