P12193 [NOISG 2025 Prelim] Ducks And Buttons

**C++ 用户注意：由于此问题中涉及的整数数值较大，可能需要使用 `long long` 数据类型来代替 `int` 数据类型。** Shor 小鸭正在和他的朋友们玩一个游戏！这个游戏是在一个一维的网格上进行的，该网格由 $n$ 个单元格排成一行组成，从左到右编号为 $1$ 到 $n$。 每个单元格上都有一个按钮。如果某一时刻在第 $i$ 个单元格上有不少于 $a[i]$ 只鸭子，那么该单元格上的按钮就会被永久按下。即使这些鸭子离开了，该按钮也仍然保持按下状态。为了赢得这场游戏，所有 $n$ 个按钮都必须被按下。 一开始，第 $1$ 个单元格上有 $d$ 只鸭子。每次移动中，一只鸭子可以向左或向右移动一个单元格。 请确定赢得这场游戏所需的最少总移动次数。**题目保证存在某种移动方式可以赢得这场游戏。**

无

无

### 子任务 对于所有测试用例，输入将满足以下约束条件： - $1 \leq n \leq 200\,000$ - $1 \leq d \leq 10^9$ - 对于所有 $1 \leq i \leq n$，都有 $0 \leq a[i] \leq d$ - 题目保证存在某种移动方式可以赢得这场游戏 你的程序将在满足以下特殊性质的输入数据上进行测试： | 子任务 | 分值 | 特殊性质 | | :-: | :-: | :-: | | $0$ | $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$。