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?

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 $ .

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.

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 $ .