CF2259G.Index Removal

An array $b_1, b_2, \ldots, b_m$ is good if, for each $i$ $(1 \leq i \lt m)$, $b_{i+1} \geq b_i$ and $b_{i+1} - b_i \leq k$. An array of length $1$ is always good.

You are given an initially good array $a_1, a_2, \ldots, a_n$. Solve the following problem for each $i$ $(1 \leq i \leq n)$ independently:

• The $i$-th element of $a$ is removed, making $a = [a_1, a_2, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n]$. In one operation, you are able to subtract $1$ from any element of $a$. What is the minimum number of operations required to make $a$ good again?

数组 $b_1, b_2, \ldots, b_m$ 被称为好数组，当且仅当对每个 $i$（$1 \leq i \lt m$），均满足 $b_{i+1} \geq b_i$ 且 $b_{i+1} - b_i \leq k$。长度为 $1$ 的数组恒为好数组。

给定一个初始的好数组 $a_1, a_2, \ldots, a_n$。对每个 $i$（$1 \leq i \leq n$），独立求解如下问题：

• 删除 $a$ 的第 $i$ 个元素，得到 $a = [a_1, a_2, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n]$。每次操作允许将 $a$ 中任意一个元素减 $1$。问：使 $a$ 再次成为好数组所需的最少操作次数是多少？

The first line of each input contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($2 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$). It is guaranteed that $a$ is initially good.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每组输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 2 \cdot 10^5$，$1 \leq k \leq 10^9$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）。保证初始数组 $a$ 是“好的”。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output $n$ space separated integers on a single line: the $i$-th integer denoting the solution to the problem for the $i$-th index.

对于每个测试用例，在一行中输出 $n$ 个以空格分隔的整数：第 $i$ 个整数表示该问题在第 $i$ 个下标处的解。

In the first test case:

• $i = 1$, $a = [2, 4, 5]$. Since $a$ is still good, we do not need to perform any operations.
• $i = 2$, $a = [1, 4, 5]$. If we perform the operation once on the $2$nd element, $a = [1, 3, 5]$, which is a good array.
• $i = 3$, $a = [1, 2, 5]$. If we perform the operation once on the $3$rd element, $a = [1, 2, 4]$, which is a good array.
• $i = 4$, $a = [1, 2, 4]$. Since $a$ is still good, we do not need to perform any operations.

In the fourth test case, $a$ will remain good no matter what element we remove, so the answer for each index is $0$.

在第一个测试用例中：

• $i = 1$，$a = [2, 4, 5]$。由于 $a$ 仍是好数组，因此无需执行任何操作。
• $i = 2$，$a = [1, 4, 5]$。若对第 $2$ 个元素执行一次操作，则 $a = [1, 3, 5]$，这是一个好数组。
• $i = 3$，$a = [1, 2, 5]$。若对第 $3$ 个元素执行一次操作，则 $a = [1, 2, 4]$，这是一个好数组。
• $i = 4$，$a = [1, 2, 4]$。由于 $a$ 仍是好数组，因此无需执行任何操作。

在第四个测试用例中，无论移除哪个元素，$a$ 始终保持为好数组，因此每个下标对应的答案均为 $0$。