CF1852C.Ina of the Mountain

To prepare her "Takodachi" dumbo octopuses for world domination, Ninomae Ina'nis, a.k.a. Ina of the Mountain, orders Hoshimachi Suisei to throw boulders at them. Ina asks you, Kiryu Coco, to help choose where the boulders are thrown.

There are $n$ octopuses on a single-file trail on Ina's mountain, numbered $1, 2, \ldots, n$. The $i$-th octopus has a certain initial health value $a_i$, where $1 \leq a_i \leq k$.

Each boulder crushes consecutive octopuses with indexes $l, l+1, \ldots, r$, where $1 \leq l \leq r \leq n$. You can choose the numbers $l$ and $r$ arbitrarily for each boulder.

For each boulder, the health value of each octopus the boulder crushes is reduced by $1$. However, as octopuses are immortal, once they reach a health value of $0$, they will immediately regenerate to a health value of $k$.

Given the octopuses' initial health values, find the minimum number of boulders that need to be thrown to make the health of all octopuses equal to $k$.

为了让她麾下的“Takodachi”呆萌章鱼们为统治世界做好准备，九十九七奈（ aka 山之伊娜）命令星街彗星向这些章鱼投掷巨石。伊娜请你——桐生可可——协助决定巨石的投掷位置。

在伊娜的山中有一条单列小径，上面排列着 $n$ 只章鱼，编号为 $1, 2, \ldots, n$。第 $i$ 只章鱼具有初始生命值 $a_i$，其中 $1 \leq a_i \leq k$。

每块巨石会碾压一段连续的章鱼，其编号为 $l, l+1, \ldots, r$，其中 $1 \leq l \leq r \leq n$。对于每块巨石，你可以任意选定 $l$ 和 $r$。

每块巨石会使它所碾压的每只章鱼的生命值减少 $1$。然而，由于章鱼是不朽的，一旦某只章鱼的生命值降至 $0$，它将立即再生并恢复至生命值 $k$。

给定章鱼们的初始生命值，请计算使所有章鱼生命值均变为 $k$ 所需投掷的最少巨石数量。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le 10^9$) – the number of octopuses, and the upper bound of a octopus's health value.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$) – the initial health values of the octopuses.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le 10^9$）——分别表示章鱼的数量以及章鱼生命值的上限。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le k$）——表示各章鱼的初始生命值。

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

For each test case, output the minimum number of boulders that need to be thrown to make the health values of all octopuses equal to $k$.

对于每个测试用例，输出使所有章鱼的生命值均等于 $k$ 所需投掷的石块的最小数量。

In the first test case, the minimum number of boulders thrown is $2$:

• Throw the first boulder between $[l,r] = [1,3]$. Then, the octopuses' health values become $[3, 1, 3, 3]$.
• Throw the second boulder between $[l,r] = [2,2]$. Then, the octopuses' health values become $[3, 3, 3, 3]$.

In the second test case, the minimum number of boulders thrown is $4$. The $[l,r]$ ranges are $[1,7], [2, 6], [3, 5], [4, 4]$.

在第一个测试用例中，投掷巨石的最小数量为 $2$：

• 第一次在区间 $[l,r] = [1,3]$ 内投掷巨石。此时章鱼的生命值变为 $[3, 1, 3, 3]$。
• 第二次在区间 $[l,r] = [2,2]$ 内投掷巨石。此时章鱼的生命值变为 $[3, 3, 3, 3]$。

在第二个测试用例中，投掷巨石的最小数量为 $4$。对应的 $[l,r]$ 区间分别为 $[1,7], [2, 6], [3, 5], [4, 4]$。