「GLR-R3」惊蛰

  「微雨众卉新，一雷惊蛰始」 ---   中午，休息室，阿绫肩膀上。   “我有一个愿望，参加全国音乐祭，获奖，和阿绫一起，摆脱这训练的苦海。”   “为热爱而到来，为抽身而努力……吗”。   正午的阳光渗过窗帘，抚上困倦的人儿的脸颊。天依的左手悄悄搭上阿绫怀里的吉他，   “铮——”   蛰虫被雷声唤醒，没人向他们保证雨的降临。 ---   **惊蛰** 「我愿把岁月磨成望镜寻遍这星空　将微光聚焦手心紧紧握住不放松」

比赛临近，各式测试也丰富了起来，作为天依他们的专业分析师，你的工作是统计分析队员们表现情况——总之，某领导要来慰问，所以你被要求修改出一份令人赏心悦目的分析报告。 在已有的 $n$ 次测试中，对于某位特定的选手，他在第 $i$ 次测试的**波动值**是非负整数 $a_i$。波动值越小表示选手在测试中的心态和发挥越稳定，所以你需要“略微调整”波动值序列 $\{a_n\}$，得到另一个非负整数序列 $\{b_n\}$。不过，做人不能昧良心，但报告又必须好看，所以 $\{b_n\}$ 有如下要求： - $\{b_n\}$ **单调不递增**，选手越来越厉害嘛； - 对于每个 $i$，如果 $b_i<a_i$，老师会不高兴，所以你需要花费 $C$ 单位的精力说服老师（其中 $C$ 为给定常数）； - 对于每个 $i$，如果 $a_i\le b_i$，选手会不高兴，而且可能很不高兴，所以你需要花费 $b_i-a_i$ 单位的精力安慰选手。 你希望在满足条件的情况下，**最小化**花费的精力之和。作为成熟的信竞选手，你自然需要自己动手，求出这一最小化的结果。 #### 形式化题意 给定非负整数序列 $\{a_n\}$，定义函数 $f(x,y)$ 为 $$ f(x,y)=\begin{cases} x-y,&x\ge y\\ C,&x< y \end{cases}, $$ 其中 $C$ 是给定常数。请构造一个**不增**非负整数序列 $\{b_n\}$，最小化 $$ \sum_{i=1}^nf(b_i,a_i). $$ 你仅需输出这一最小化的结果。

第一行两个整数，表示序列长度 $n$ 和给定常数 $C$。 接下来一行表示序列 $\{a_n\}$ 。

输出一行一个整数，表示最小化的结果。

3 3
4 5 2

1

10 5
12 17 20 2 0 1 13 6 10 1

26

#### 样例 #1 解释 构造 $\{b_n\}=\{5,5,2\}$，可见： $$ \begin{aligned} \sum_{i=1}^nf(b_i,a_i) &= f(5,4)+f(5,5)+f(2,2)\\ &= 1+0+0\\ &= 1. \end{aligned} $$ #### 样例 #2 解释 构造 $\{b_n\}=\{12,11,4,2,1,1,1,1,1,1\}$，可以得到答案。 ### 数据规模与约定 **本题采用 Subtask 的计分方式。** 设 $V$ 为序列 $\{a_n\}$ 中元素以及常数 $C$ 的值域。 对于 $100\%$ 的数据，$1\le n\le10^6$，$V\subseteq[0,10^9]$。 对于不同的子任务，作如下约定： | 子任务编号 | $n$ | $V$ | 特殊性质 | 子任务分值 | | :--------: | :-------: | :-------------: | :------: | :--------: | | $1$ | $\le10^3$ | $\subseteq[0,10^9]$ | 无 | $25$ | | $2$ | $\le10^5$ | $\subseteq[0,10^2]$ | 无 | $15$ | | $3$ | $\le10^6$ | $\subseteq[0,10^9]$ | **A** | $5$ | | $4$ | $\le10^6$ | $\subseteq[0,10^9]$ | **B** | $15$ | | $5$ | $\le10^5$ | $\subseteq[0,10^9]$ | 无 | $20$ | | $6$ | $\le10^6$ | $\subseteq[0,10^9]$ | 无 | $20$ | - **特殊性质 A**：对于常数 $C$ ，满足 $C = 0$。 - **特殊性质 B**：对于序列 $\{a_n\}$ ，满足元素单调**递增**。