Nastya 烤了 $$$m$$$ 煎饼并将其铺在 $$$n$$$ 菜肴上。菜品排成一排,从左到右编号。她将 $$$a_i$$$ 煎饼放在索引为 $$$i$$$ 的盘子上。
看到菜肴后,弗拉德决定整理堆栈并移走一些煎饼。只需一步,他就可以将任意菜肴中的一张煎饼移至最接近的菜肴,即选择菜肴 $$$i$$$ ($$$a_i > 0$$$) 并执行以下操作之一:
- 如果 $$$i > 1$$$,将煎饼放在具有先前索引的盘子上,在此移动之后 $$$a_i = a_i - 1$$$ 和 $$$a_{i - 1} = a_{i - 1} + 1$$$;
- 如果 $$$i < n$$$,将煎饼放在具有以下索引的盘子上,在此移动之后 $$$a_i = a_i - 1$$$ 和 $$$a_{i + 1} = a_{i + 1} + 1$$$。
Vlad 希望在移动尽可能少的煎饼后,使数组 $$$a$$$ 不再增加。帮助他找到所需的最少移动次数。
如果 $$$a_i \ge a_{i+1}$$$ 对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$i$$$ 来说,数组 $$$a=[a_1, a_2,\dots,a_n]$$$ 被称为非增数组。
输入
输入的第一行包含两个数字 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 250$$$) — 分别是菜肴的数量和煎饼的数量。
第二行包含$$$n$$$ 数字$$$a_i$$$ ($$$0 \le a_i \le m$$$),所有$$$a_i$$$ 的总和等于$$$m$$$。
输出
打印单个数字:使数组 $$$a$$$ 不递增所需的最小移动次数。
示例
输入 #1
6 19 5 3 2 3 3 3
输出 #1
2
输入 #2
3 6 3 2 1
输出 #2
0
输入 #3
3 6 2 1 3
输出 #3
1
输入#4
6 19 3 4 3 3 5 1
输出#4
3
输入 #5
10 1 0 0 0 0 0 0 0 0 0 1
输出 #5
9
注意
在第一个示例中,您首先需要将煎饼从盘 $$$1$$$ 中移出,然后 $$$a = [4, 4, 2, 3, 3, 3]$$$。之后,你需要将煎饼从菜$$$2$$$移到菜$$$3$$$,数组将变成非增长$$$a = [4, 3, 3, 3, 3, 3]$$$。