题目描述

光头强烤了 $m$ 个煎饼，分别放在 $n$ 个盘子里。这些盘子在一排中，从左到右编号。她在第 $i$ 个盘子上放了 $a_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$。

光头强希望在移动尽可能少的煎饼的情况下使数组 $a$ 成为非递增的。帮他找出实现这一点所需的最小移动次数。

当且仅当对于所有 $i∈[1, n−1]$，都有 $a_i≥a_{i+1}$ 时，数组 $a=[a1,a2,…,an]$ 称为非递增的。

输入格式

第一行输入两个数字 $n$ 和 $m(1≤n,m≤250)$— 菜肴和煎饼的数量。

第二行包含 $n$ 个数字 $a_i(0≤a_i≤m)$，所有 $a_i$ 的和等于 $m$。

输出格式

输出一个数字：使数组 $a$ 非递增所需的最小移动次数。

测试样例

6 19
5 3 2 3 3 3

2

3 6
3 2 1

0

3 6
2 1 3

1

6 19
3 4 3 3 5 1

3

10 1
0 0 0 0 0 0 0 0 0 1

9

样例说明

在第一个例子中，光头强需要先将第一个盘子的薄饼移到第二个盘子，这样 $a$ 就变成了 $[4,4,2,3,3,3]$。然后你需要将第二个盘子的薄饼移到第三个盘子，这样 $a$ 就变成了非递增数组 $a=[4,3,3,3,3,3]$。