Problem Description

You are given a non-decreasing integer sequence $\{a_i\}$ of length $n$ and an integer $k$.

We define the "difference measure" of two sequences $\{x_i\}, \{y_i\}$ of the same length $p$ as $F(x,y,p)=\sum_{i=1}^p |x_i-y_i|$.

Now, for each integer $l \in [1,n]$, you need to construct a sequence $\{b_{l,i}\}$ of length $l$, such that for any $1\le i < l$, $b_{l,i+1}\ge b_{l,i}+k$, and $F(a_{[1\cdots l]},b_l,l)$ is minimized. Here, $a_{[1\cdots l]}$ denotes the prefix of $\{a_i\}$ with length $l$, i.e., $\{a_1,a_2,\cdots,a_l\}$. Note that $b_{l,i}$ does not have to be an integer.

Input Format

The first line contains two integers $n, k$.
The second line contains $n$ integers, representing $\{a_i\}$.
The third line contains an integer $T$, which specifies the output mode. See the "Output Format" for details.

Output Format

• If $T=0$, output $n$ integers, one per line. The integer on line $l$ represents $F(a_{[1\cdots l]},b_l,l)$.
• If $T=1$, you only need to output one integer on a single line, which is $F(a,b_n,n)$.

5 2
2 3 4 5 6
0

0
1
2
4
6

6 2
1 1 4 5 6 8
0

0
2
2
3
4
5

6 2
1 1 4 5 6 8
1

5

20 4
4 6 7 9 19 21 30 32 33 35 49 50 58 67 75 77 78 89 91 91
0

0
2
5
10
10
12
12
14
17
22
22
25
25
25
25
27
30
30
32
36

Hint

Sample Explanation

Sample #1

One possible construction is:

$$\begin{aligned} b_1&=\{2\}\\ b_2&=\{2,4\}\\ b_3&=\{1,3,5\}\\ b_4&=\{1,3,5,7\}\\ b_5&=\{0,2,4,6,8\}\\ \end{aligned}$$

Sample #2

One possible construction is:

$$\begin{aligned} b_1&=\{1\}\\ b_2&=\{0,2\}\\ b_3&=\{0,2,4\}\\ b_4&=\{0,2,4,6\}\\ b_5&=\{-1,1,3,5,7\}\\ b_6&=\{-1,1,3,5,7,9\}\\ \end{aligned}$$

Sample #3

Same as Sample #2, except that $T=1$. You only need to output $F(a,b_6,6)=5$.

Constraints and Notes

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|} \hline \textbf{subtask} & \textbf{Score} & \bm{{n\le}} & \bm{{T=}} & \bm{{k,a_i\le}} & \textbf{subtask dependencies}\cr\hline 1 & 30 & 100 & 0 & 100 & -\cr\hline 2 & 30 & 10^5 & 0 & 10^6 & 1\cr\hline 3 & 40 & 10^6 & 1 & 10^6 & -\cr\hline \end{array}$$

For $100\%$ of the testdata, $1\le n \le 10^6$, $1\le k,a_i\le 10^6$, and $T\in\{0,1\}$.

Translated by ChatGPT 5