叠垒残骸

扰动算完了，但通道里堆满了金属残骸——塌方的墙壁、碎裂的管道、废弃的零件。

"要清理。"CC说，"不然过不去。"

"咋清理？"

"叠起来。"你说，"从后往前，一层一层垒。每层总宽度不能超过下一层——不然会塌。"

"倒序？"

"对。"你说，"从终点往回堆。最后一块地基最宽，上面一层比一层窄。"

"像金字塔。"

"对。"你说，"但用废金属堆的。"

"最多能堆几层？"

"$dp[i]$为以第$i$块残骸为顶层时的最小宽度。"你说，"$dp[i]=\min(sum[i]-sum[j])$，且$sum[i]-sum[j]\ge dp[j]$。"

"也就是这层要比下一层窄。"

"对。"

"单调队列优化。"

"对。"

你开始写。倒序处理，单调队列维护可行决策点。

"最后一块。"你说，"宽度10。$dp[n]=10$。"

"倒数第二块。"你说，"宽度5。可以和最后一块叠——$5<10$，可以。$dp[n-1]=5$。"

"倒数第三块。"你说，"宽度8。不能叠在倒数第二块上——$8>5$。只能直接叠在最后一块上——$8<10$，可以。$dp[n-2]=8$。"

"三层。"

"对。"

CC开始搬——一块一块地摞。她的金属手臂在废金属中穿梭，像机械臂在管道里穿行。

"我搬底层。"她说，"你们往上加。"

"底层最宽。"

"对。"她说，"我力气大。"

Echo用投影标记每一块的位置——蓝色光点飘在残骸上，像萤火虫。

"这块放这。"她说，"那块放那。"

"你看得见？"

"我感觉得到。"她说，"每一块金属都有温度——有的凉，有的热。"

"热的？"

"刚塌下来的。"她说，"还有摩擦的余温。"

你们堆了两个小时。一座歪歪扭扭的金属塔，从地面堆到天花板。

"几层？"CC问。

"47层。"你说。

"又是47。"

"对。"你说，"47层，47步，47个希望。"

"够了。"CC说，"够我们爬上去。"

"爬上去？"

"上面有个通风口。"她说，"通往Zero核心。"

题目描述

给定$n$个残骸的宽度，要从后往前分成若干层。每层总宽不能超过下一层。求最多能分几层。

输入格式

$n$。然后$n$个整数表示宽度。

输出格式

最多层数。

输入样例

3
1 2 3

输出样例

2

提示

• 倒序DP。
• $dp[i]$为以$i$为顶层的最小宽度。
• $dp[i]=\min(sum[i]-sum[j])$，且$sum[i]-sum[j]\ge dp[j]$。
• 单调队列优化。