调兵遣将

矿区清扫完了，但Zero的防御部队还在——自动巡逻的哨兵，分布在核心区的各个要塞。

"要打。"CC说，"但不是硬打。要调兵遣将——把兵力用在刀刃上。"

"咋调？"

"分段树。"你说，"每个要塞有一个防御值。我们要攻下一段连续的要塞，总攻击值要超过它们的总防御值。"

"一段一段打？"

"对。"你说，"用线段树维护每个区间的防御值之和。然后找最弱的一段，集中兵力突破。"

"最弱？"

"对。"你说，"$dp[i]$为攻下前$i$个要塞的最小兵力。$dp[i]=\min(dp[j]+cost(j+1,i))$。"

"$cost$是啥？"

"$cost(j+1,i)$是这段要塞的总防御值。"你说，"如果我们的兵力超过它，就能攻下。"

"线段树维护区间和。"

"对。"

你开始写。先建线段树，然后DP。

"第一个要塞。"你说，"防御值10。"

"第二个。"你说，"防御值5。"

"第三个。"你说，"防御值8。"

"攻下1到2。"你说，"总防御15。$dp[2]=dp[0]+15=15$。"

"攻下3。"你说，"$dp[3]=dp[2]+8=23$。"

"或者攻下1到3。"你说，"总防御23。$dp[3]=dp[0]+23=23$。"

"一样。"

"但如果有第四个。"你说，"防御值3。攻下3到4，总防御11。$dp[4]=dp[2]+11=26$。"

"比单独攻3和4省2。"

"对。"你说，"这就是分段的好处——合并弱的，省兵力。"

"集中兵力，各个击破。"

"对。"CC说，"这是打仗的基本。"

她举起数据刀——刀尖在灯光下闪着寒光。

"我打头阵。"她说，"你们跟紧。"

"你一个人？"

"我探路。"她说，"找到弱的，叫你们。"

"那你小心。"

"放心。"她说，"我能打。"

题目描述

给定$n$个要塞，第$i$个防御值为$a_i$。要攻下一段连续的要塞，总攻击值必须超过总防御值。求攻下全部要塞的最小总兵力。

输入格式

$n$。然后$n$个整数。

输出格式

最小总兵力。

输入样例

5
1 2 3 4 5

输出样例

Case #1: 0
Case #2: 0
Case #3: 0
Case #4: 0
Case #5: 0

提示

• 线段树优化DP。
• $dp[i]$为攻下前$i$个的最小兵力。
• $dp[i]=\min(dp[j]+sum(j+1,i))$。
• 用线段树维护区间和，快速查询。