A. 鸭子与按钮

题目背景

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

题目描述

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

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

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

输入格式

输入以如下格式从标准输入中给出。

$n$ $d$ $a[1]\;a[2]\;\dots\;a[n]$

输出格式

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

样例

2 199
175 42

42

5 3
1 1 0 1 0

3

5 7
2 2 2 2 2

8

7 5
1 3 3 4 5 5 5

30

8 9
7 6 6 6 3 3 3 1

28

8 5
2 3 5 1 4 2 1 0

21

4 1000000000
1 1 1 999999999

2999999997

样例解释

样例 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。

数据范围

• 对于所有测试用例，输入满足：

  $1 \le n \le 200000$ $1 \le d \le 10^{9}$ $0 \le a[i] \le 10^{9}$ 保证存在某种移动方式可以赢得这场游戏

• 子任务：

  子任务	分值	特殊性质
  1	8	$n=2$
  2	5	$a[i]=0$
  3	11	$a[i]\le 1$
  4	6	所有 $a[i]$ 值相等
  5	19	$n,d\le 1000$
  6	12	$a[i]$ 单调不减
  7	16	$a[i]$ 单调不升
  8	23	无