CF2053H.Delicate Anti-monotonous Operations

I shall be looking for you who would be out of Existence.

— HyuN, Disorder

There are always many repetitive tasks in life. Iris always dislikes them, so she refuses to repeat them. However, time cannot be turned back; we only have to move forward.

Formally, Iris has an integer sequence $a_1, a_2, \ldots, a_n$, where each number in the sequence is between $1$ and $w$, inclusive. It is guaranteed that $w \geq 2$.

Iris defines an operation as selecting two numbers $a_i, a_{i+1}$ satisfying $a_i = a_{i+1}$, and then changing them to two arbitrary integers within the range $[1, w]$. Iris does not like equality, so she must guarantee that $a_i \neq a_{i+1}$ after the operation. Two identical pairs $a_i, a_{i+1}$ can be selected multiple times.

Iris wants to know the maximum possible sum of all elements of $a$ after several (possible, zero) operations, as well as the minimum number of operations required to achieve this maximum value.

我将寻找那已不复存在的你。

—— HyuN，《Disorder》（feat. Yuri），K-SOUNDS STUDIO

生活中总有许多重复的任务。Iris 一向讨厌重复，因此她拒绝重复执行它们。然而，时光无法倒流；我们只能向前迈进。

形式化地，Iris 拥有一个整数序列 $a_1, a_2, \ldots, a_n$，其中序列中每个数均在 $[1, w]$ 范围内（含端点）。题目保证 $w \geq 2$。

Iris 将一次操作定义为：选取两个相邻元素 $a_i, a_{i+1}$，满足 $a_i = a_{i+1}$，然后将它们同时替换为 $[1, w]$ 范围内的任意两个整数。由于 Iris 不喜欢相等，因此操作后必须保证 $a_i \neq a_{i+1}$。相同的相邻对 $a_i, a_{i+1}$ 可被多次选取。

Iris 想知道：经过若干次（可能为零次）操作后，序列 $a$ 所有元素之和所能达到的最大值，以及达成该最大值所需的最少操作次数。

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

The first line of each test case contains two integers $n$ and $w$ ($1 \leq n \leq 2\cdot 10^5$, $2 \leq w \leq 10^8$) — the length of the array, and the maximum allowed value of the elements.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq w$) — the elements in the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

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

每个测试用例的第一行包含两个整数 $n$ 和 $w$（$1 \leq n \leq 2\cdot 10^5$，$2 \leq w \leq 10^8$）—— 数组的长度以及元素允许的最大值。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq w$）—— 数组中的元素。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

For each test case, output two integers — the maximum possible sum of all elements of $a$ and the minimum number of operations required, respectively.

对于每个测试用例，输出两个整数——数组 $a$ 所有元素之和的最大可能值，以及所需的最少操作次数。

In the first test case, no operation can be performed so the answers are $\sum a_i = 15$ and $0$, respectively.

In the second test case, the operations can be performed as follows:

\[3, 1, 2, 3, 4, \\underline{1, 1}\] \\rightarrow \[3, 1, 2, 3, \\underline{4, 4}, 5\] \\rightarrow \[3, 1, 2, \\underline{3, 3}, 5, 5\] \\rightarrow \[3, 1, \\underline{2, 2}, 5, 5, 5\] \\rightarrow \[3, \\underline{1, 1}, 5, 5, 5, 5\] \\rightarrow \[\\underline{3, 3}, 5, 5, 5, 5, 5\] \\rightarrow \[4, 5, 5, 5, 5, 5, 5\]

It can be shown this is optimal, so we should output $\sum a_i = 34$ and the number of operations, $6$, respectively.

在第一个测试用例中，无法执行任何操作，因此答案分别为 $\sum a_i = 15$ 和 $0$。

在第二个测试用例中，操作可按如下方式进行：

\[3, 1, 2, 3, 4, \\underline{1, 1}\] \\rightarrow \[3, 1, 2, 3, \\underline{4, 4}, 5\] \\rightarrow \[3, 1, 2, \\underline{3, 3}, 5, 5\] \\rightarrow \[3, 1, \\underline{2, 2}, 5, 5, 5\] \\rightarrow \[3, \\underline{1, 1}, 5, 5, 5, 5\] \\rightarrow \[\\underline{3, 3}, 5, 5, 5, 5, 5\] \\rightarrow \[4, 5, 5, 5, 5, 5, 5\]

可以证明该方案是最优的，因此我们应分别输出 $\sum a_i = 34$ 和操作次数 $6$。