310572: CF1853E. Ina of the Mountain

E. Ina of the Mountaintime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

Input

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

Output

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

ExampleInput

2
4 3
1 2 1 3
7 3
1 2 3 1 3 2 1

Output

2
4

Note

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

题目大意：
Ninomae Ina'nis（山之伊奈）为了准备她的“Takodachi”长臂章鱼以征服世界，命令Hoshimachi Suisei向它们投掷巨石。你需要帮助选择投掷巨石的位置。有n只章鱼排成一行在伊奈的山上，编号为1, 2, ..., n。第i只章鱼有一个初始的生命值a_i，其中1 ≤ a_i ≤ k。每个巨石会压碎索引为l, l+1, ..., r的连续章鱼，你可以任意选择每个巨石的l和r。对于每个巨石，被压碎的每只章鱼的生命值都会减少1。但是，由于章鱼是不朽的，一旦它们的生命值达到0，它们将立即恢复到生命值为k。给定章鱼的初始生命值，找出使所有章鱼的生命值等于k所需投掷的最小巨石数量。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^5），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数n和k（1 ≤ n ≤ 2 * 10^5，1 ≤ k ≤ 10^9），分别是章鱼的数量和章鱼生命值的上限。
- 第二行包含n个整数a_1, a_2, ..., a_n（1 ≤ a_i ≤ k），表示章鱼的初始生命值。
- 保证所有测试用例中n的总和不超过2 * 10^5。

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

示例：
输入：
2
4 3
1 2 1 3
7 3
1 2 3 1 3 2 1

输出：
2
4

注意：
- 在第一个测试用例中，最少需要投掷2个巨石：首先在[1,3]范围内投掷一个巨石，然后章鱼的生命值变为[3, 1, 3, 3]；接着在[2,2]范围内投掷第二个巨石，生命值变为[3, 3, 3, 3]。
- 在第二个测试用例中，最少需要投掷4个巨石，范围分别是[1,7], [2, 6], [3, 5], [4, 4]。题目大意： Ninomae Ina'nis（山之伊奈）为了准备她的“Takodachi”长臂章鱼以征服世界，命令Hoshimachi Suisei向它们投掷巨石。你需要帮助选择投掷巨石的位置。有n只章鱼排成一行在伊奈的山上，编号为1, 2, ..., n。第i只章鱼有一个初始的生命值a_i，其中1 ≤ a_i ≤ k。每个巨石会压碎索引为l, l+1, ..., r的连续章鱼，你可以任意选择每个巨石的l和r。对于每个巨石，被压碎的每只章鱼的生命值都会减少1。但是，由于章鱼是不朽的，一旦它们的生命值达到0，它们将立即恢复到生命值为k。给定章鱼的初始生命值，找出使所有章鱼的生命值等于k所需投掷的最小巨石数量。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^5），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数n和k（1 ≤ n ≤ 2 * 10^5，1 ≤ k ≤ 10^9），分别是章鱼的数量和章鱼生命值的上限。 - 第二行包含n个整数a_1, a_2, ..., a_n（1 ≤ a_i ≤ k），表示章鱼的初始生命值。 - 保证所有测试用例中n的总和不超过2 * 10^5。 输出： - 对于每个测试用例，输出使所有章鱼的生命值等于k所需投掷的最小巨石数量。 示例： 输入： 2 4 3 1 2 1 3 7 3 1 2 3 1 3 2 1 输出： 2 4 注意： - 在第一个测试用例中，最少需要投掷2个巨石：首先在[1,3]范围内投掷一个巨石，然后章鱼的生命值变为[3, 1, 3, 3]；接着在[2,2]范围内投掷第二个巨石，生命值变为[3, 3, 3, 3]。 - 在第二个测试用例中，最少需要投掷4个巨石，范围分别是[1,7], [2, 6], [3, 5], [4, 4]。