Shor 小鸭正在和他的朋友们玩一个游戏！这个游戏是在一个一维的网格上进行的，该网格由 $n$ 个单元格排成一行组成，从左到右编号为 $1$ 到 $n$。

每个单元格上都有一个按钮。如果某一时刻在第 $i$ 个单元格上有不少于 $a [ i ]$ 只鸭子，那么该单元格上的按钮就会被永久按下。即使这些鸭子离开了，该按钮也仍然保持按下状态。为了赢得这场游戏，所有 $n$ 个按钮都必须被按下。

一开始，第 $1$ 个单元格上有 $d$ 只鸭子。每次移动中，一只鸭子可以向左或向右移动一个单元格。

请确定赢得这场游戏所需的最少总移动次数。题目保证存在某种移动方式可以赢得这场游戏。

输入格式

输入的第一行包含两个用空格分隔的整数 $n$ 和 $d$。

第二行包含 $n$ 个用空格分隔的整数 $a [ 1 ] , a [ 2 ] , \ldots , a [ n ]$。

输出格式

输出一个整数，表示赢得这场游戏所需的最少总移动次数。

输入输出样例 #1

输入 #1

2 199
175 42

输出 #1

42

输入输出样例 #2

输入 #2

5 3
1 1 0 1 0

输出 #2

3

输入输出样例 #3

输入 #3

5 7
2 2 2 2 2

输出 #3

8

输入输出样例 #4

输入 #4

7 5
1 3 3 4 5 5 5

输出 #4

30

输入输出样例 #5

输入 #5

8 9
7 6 6 6 3 3 3 1

输出 #5

28

输入输出样例 #6

输入 #6

8 5
2 3 5 1 4 2 1 0

输出 #6

21

输入输出样例 #7

输入 #7

4 1000000000
1 1 1 999999999

输出 #7

2999999997

说明/提示

子任务

对于所有测试用例，输入将满足以下约束条件：

• $1 \le n \le 200 000$
• $1 \le d \le 10^{9}$
• 对于所有 $1 \le i \le n$，都有 $0 \le a [ i ] \le d$
• 题目保证存在某种移动方式可以赢得这场游戏

你的程序将在满足以下特殊性质的输入数据上进行测试：

样例 1 解释

此样例适用于子任务 $1 , 5 , 7 , 8$。

样例 2 解释

此样例适用于子任务 $3 , 5 , 8$。

样例 3 解释

此样例适用于子任务 $4 , 5 , 6 , 7 , 8$。

样例 4 解释

此样例适用于子任务 $5 , 6 , 8$。

样例 5 解释

此样例适用于子任务 $5 , 7 , 8$。

样例 6 解释

此样例适用于子任务 $5 , 8$。

下图展示了一种可以最小化总移动次数的移动序列。每一个红色箭头代表一次移动，箭头上方的数字表示移动的顺序，移动 $1$ 最先发生。

• 按钮 $1$ 在所有移动发生之前就已被按下。
• 按钮 $2$ 在第 $3$ 次移动后被按下。
• 按钮 $3$ 在第 $10$ 次移动后被按下。
• 按钮 $4$ 在第 $11$ 次移动后被按下。
• 按钮 $5$ 在第 $18$ 次移动后被按下。
• 按钮 $6$ 在第 $20$ 次移动后被按下。
• 按钮 $7$ 在第 $21$ 次移动后被按下。
• 按钮 $8$ 在所有移动发生之前就已被按下（因为 $a [ 8 ] = 0$）。

由于在第 $21$ 次移动结束后所有按钮都已被按下，因此 $21$ 次移动是足够的。可以证明这是赢得游戏所需的最少移动次数。

样例 7 解释

此样例适用于子任务 $4 , 6 , 8$。