题目描述

C++ 用户注意：由于此问题中涉及的整数数值较大，可能需要使用 long long 数据类型来代替 int 数据类型。

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

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

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

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

输入格式

你的程序必须从标准输入读取数据。

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

第二行包含 $n$ 个用空格分隔的整数 $a[1], a[2], \ldots, 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 \leq n \leq 200\,000$
• $1 \leq d \leq 10^9$
• 对于所有 $1 \leq i \leq n$，都有 $0 \leq a[i] \leq d$
• 题目保证存在某种移动方式可以赢得这场游戏

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

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

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