分数: 300 点
问题陈述
有 N 盒子排列成一排。 最初, i左边第一个框包含 a_i 糖果。
Snuke 可以执行任意多次以下操作:
- 选择一个至少装有一颗糖果的盒子,然后吃掉所选盒子中的一颗糖果。
他的目标如下:
- 任何两个相邻的盒子最多包含 总共 x 糖果。
找出实现目标所需的最少操作数。
约束
- 2 ≤ N ≤ 10^5
- 0 ≤ a_i ≤ 10^9
- 0 ≤ x ≤ 10^9
输入
输入由标准输入按以下格式给出:
N x a_1 a_2 ... a_N
输出
打印实现目标所需的最少操作数。
示例输入 1
3 3 2 2 2
示例输出 1
1
吃第二个盒子里的一颗糖果。 那么每个盒子里的糖果数量就变成了 (2, 1, 2).
示例输入 2
6 1 1 6 1 2 0 4
示例输出 2
11
例如,吃第二个盒子里的六颗糖果,第四个盒子里的两颗糖果,第六个盒子里的三颗糖果。 那么每个盒子里的糖果数量就变成了 (1, 0, 1, 0, 0, 1).
示例输入 3
5 9 3 1 4 1 5
示例输出 3
0
无需执行操作即可实现目标。
示例输入 4
2 0 5 5
示例输出 4
10
所有糖果都需要吃掉。