D. Вставь прогрессию
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность из $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$. Также даны $$$x$$$ целых чисел $$$1, 2, \dots, x$$$.

Вас просят вставить каждое из этих дополнительных целых чисел в последовательность $$$a$$$. Каждое число можно вставлять в начало последовательности, в конец последовательности или между любыми элементами последовательности.

Счет полученной последовательности $$$a'$$$ равен сумме абсолютных разностей соседних элементов в ней $$$\left(\sum \limits_{i=1}^{n+x-1} |a'_i - a'_{i+1}|\right)$$$.

Какой наименьший счет может быть у последовательности $$$a'$$$?

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$x$$$ ($$$1 \le n, x \le 2 \cdot 10^5$$$) — длина последовательности и количество дополнительных чисел.

Во второй строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$).

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите одно целое число — наименьшую сумму абсолютных разностей соседних элементов в последовательности после того, как вы вставите в нее дополнительные числа.

Пример
Входные данные
4
1 5
10
3 8
7 2 10
10 2
6 1 5 7 3 3 9 10 10 1
4 10
1 3 1 2
Выходные данные
9
15
31
13
Примечание

Здесь представлены последовательности с наименьшим счетом в примере. Подчеркнутые элементы — это дополнительные числа. Обратите внимание, что существуют и другие последовательности с наименьшим счетом.

  • $$$\underline{1}, \underline{2}, \underline{3}, \underline{4}, \underline{5}, 10$$$
  • $$$\underline{7}, 7, \underline{6}, \underline{4}, 2, \underline{2}, \underline{1}, \underline{3}, \underline{5}, \underline{8}, 10$$$
  • $$$6, \underline{1}, 1, \underline{2}, 5, 7, 3, 3, 9, 10, 10, 1$$$
  • $$$1, 3, \underline{1}, 1, 2, \underline{2}, \underline{3}, \underline{4}, \underline{5}, \underline{6}, \underline{7}, \underline{8}, \underline{9}, \underline{10}$$$