P8476 "GLR-R3" Jingzhe

  "A light rain makes all flowers fresh; with one thunder, Jingzhe begins." ---   At noon, in the lounge, on Ayang's shoulder.   "I have a wish: to take part in the National Music Festival, win an award, and together with Ayang, break free from this bitter sea of training."   "Coming for love, working hard to get away... is that so?"   The midday sunlight seeps through the curtains and gently touches the sleepy person's cheeks. Tianyi's left hand quietly rests on the guitar in Ayang's arms,   "Zheng—"   The hibernating insects are awakened by the thunder, and no one promises them that the rain will come. ---   **Jingzhe** "I am willing to grind the years into a looking glass and search all across this starry sky, focusing the faint light into my palm and holding it tight without letting go."

The contest is getting close, and various tests have become more frequent. As the professional analyst for Tianyi and the others, your job is to do statistics and analysis of the team members' performance. In short, a certain leader is coming to visit, so you are required to revise a pleasing-looking analysis report. In the existing $n$ tests, for a particular player, their **fluctuation value** in the $i$-th test is a non-negative integer $a_i$. A smaller fluctuation value means the player's mentality and performance are more stable, so you need to "slightly adjust" the fluctuation sequence $\{a_n\}$ into another non-negative integer sequence $\{b_n\}$. However, you cannot be too dishonest, yet the report must look good, so $\{b_n\}$ must satisfy: - $\{b_n\}$ is **monotone non-increasing**, because the player is getting better and better; - For each $i$, if $b_i

The first line contains two integers, the sequence length $n$ and the given constant $C$. The next line contains the sequence $\{a_n\}$.

Output one line with one integer, the minimum value.

#### Sample #1 Explanation Construct $\{b_n\}=\{5,5,2\}$. Then: $$ \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} $$ #### Sample #2 Explanation Construct $\{b_n\}=\{12,11,4,2,1,1,1,1,1,1\}$, and you can obtain the answer. ### Constraints **This problem uses Subtask scoring.** Let $V$ be the value range of the elements in $\{a_n\}$ and the constant $C$. For $100\%$ of the data, $1\le n\le10^6$, $V\subseteq[0,10^9]$. For different subtasks, the constraints are as follows: | Subtask ID | $n$ | $V$ | Special Property | Score | | :--------: | :-------: | :-------------: | :--------------: | :---: | | $1$ | $\le10^3$ | $\subseteq[0,10^9]$ | None | $25$ | | $2$ | $\le10^5$ | $\subseteq[0,10^2]$ | None | $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]$ | None | $20$ | | $6$ | $\le10^6$ | $\subseteq[0,10^9]$ | None | $20$ | - **Special Property A**: For the constant $C$, $C = 0$. - **Special Property B**: For the sequence $\{a_n\}$, the elements are monotone **increasing**. Translated by ChatGPT 5