題目描述

小明有 n 杯水，第 i 杯水一開始為 v_i 毫升。他的目標是令到每一杯內都恰好有 k 毫升。

為達成這月標，小明有一部神奇的機器，可以讓他在一次操作中選擇若干個連續的水杯，並把這些水杯同時加上或減去 1 毫升。顯然，小明總可以用有限步操作令所有杯都為 k 毫升。請協助小明找出他最小需要操作的次數。

例如，當數列 v 是 (5, 5, 5) 時，小明可以直接選所有杯操作五次得到 (0, 0, 0)。當 v 是 (2, 2, 5, 3, 3) 、目標是 1 時，可以先選所有數操作一次得 (1, 1, 4, 2, 2)，選 (4, 2, 2) 操作一次就有 (1, 1, 3, 1, 1)，再選 (3) 做兩次就可有 (1, 1, 1, 1, 1)，故共需 4步。又譬如 v 是 (12, 11, 10, 9)、目標是 10 時，可以先選 (9) 操作一次得到 (12, 11, 10, 10)，選 (12, 11) 一次得到 (11, 10, 10, 10)，再選 (11) 一次就有 (10, 10, 10, 10)，共使用了 3 步。

(温馨提示：系統能根據完成程度給予部分分數，但若要完全解決這題需要能處理 n, k, v_i 較大的情況。)

輸入格式

第一行有一正整數 T (1 <= T <= 100)，表示接下來有 T 組獨立的測資。（需要應答 T 次）

每個測資中共兩行。第一行給定兩個整數代表一組 n k，第二行則給 n 個整數（以空格隔開），依次表示數列 v 中每個 v_i，

1 <= n <= 10⁵, 0 <= v_i <= 10⁹, 0 <= k <= 10⁹。

輸出格式

共輸出 T 行，分別為 T 個測資的答案。對第 i 個測資輸出小明最小需要操作的次數。

Samples

["4\r\n3 0\r\n5 5 5\r\n5 1\r\n2 2 5 3 3\r\n4 10\r\n12 11 10 9\r\n1 2\r\n2","5\r\n3 4\r\n5 6 5\r\n5 8\r\n9 7 9 7 9\r\n5 6\r\n10 2 8 6 9\r\n7 4\r\n9 6 8 0 6 6 4\r\n8 12\r\n10 8 4 2 2 4 8 10"]

["5\r\n4\r\n3\r\n0","2\r\n5\r\n13\r\n13\r\n10"]

提示

範例輸入#1 可見題目描述的例子。以上例子均可證明給出的步數是最小值。

!!! 用 random 猜答案是絕對無分的～

備註

BBCC 2021 口述版 （額外進化版：可以嘗試思考如何能給出一個實際操作例子）

原始資料

• Zero1 題號：a592
• Hydro 題號：Z0592
• Locale：zh_TW
• Display：open