Insert a Progression
Contest: Educational Codeforces Round 127 (Rated for Div. 2)
Difficulty rating: 1600
Tags: brute force, constructive algorithms, greedy

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. You are also given $$$x$$$ integers $$$1, 2, \dots, x$$$.

You are asked to insert each of the extra integers into the sequence $$$a$$$. Each integer can be inserted at the beginning of the sequence, at the end of the sequence, or between any elements of the sequence.

The score of the resulting sequence $$$a'$$$ is the sum of absolute differences of adjacent elements in it $$$\left(\sum \limits_{i=1}^{n+x-1} |a'_i - a'_{i+1}|\right)$$$.

What is the smallest possible score of the resulting sequence $$$a'$$$?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n, x \le 2 \cdot 10^5$$$) — the length of the sequence and the number of extra integers.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$).

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print a single integer — the smallest sum of absolute differences of adjacent elements of the sequence after you insert the extra integers into it.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Here are the sequences with the smallest scores for the example. The underlined elements are the extra integers. Note that there exist other sequences with this smallest score.

- $$$\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}$$$

Example input:
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

Example output:
9
15
31
13

Editorial:
Observe the cost of inserting a single element. Notice that inserting any value between the minimum of the sequence and the maximum of the sequence is free.
Why is this true? The argument is similar to the algorithm of finding some $$$x$$$ such that $$$f(x) = 0$$$ for a continous function $$$f$$$ if you know some $$$x_1$$$ such that $$$f(x_1) < 0$$$ and $$$x_2$$$ such that $$$f(x_2) > 0$$$.
As a more general idea, it's free to insert some value $$$s$$$ into a segment $$$[l; r]$$$ such that $$$a_l \le s$$$ and $$$s \le a_r$$$ (WLOG assume $$$a_l \le a_r$$$). Let's find the position that is free. If $$$r - l = 1$$$, then you can insert $$$s$$$ between $$$a_l$$$ and $$$a_r$$$, since it's free. Otherwise, you can choose an arbitrary position $$$l < i < r$$$. $$$s$$$ will be either between $$$a_i$$$ and $$$a_l$$$ or between $$$a_i$$$ and $$$a_r$$$ (or both of them). Descend into the one that holds to continue the search. Since the lenght decreases, at some point you will reach the segment of length $$$1$$$.
How does that help? Well, you can insert $$$1$$$ somewhere, then insert $$$x$$$ somewhere. The rest of insertions will be free.
Now it's an algorithmic problem. First, consider all options to insert both $$$1$$$ and $$$x$$$ between the same pair of elements. Next, assume you insert $$$1$$$ somewhere before $$$x$$$. Iterate from left to right, maintaning the lowest price to insert $$$1$$$. Try to insert $$$x$$$ at the current position and $$$1$$$ into the cheapest position before it. Then update the lowest price for inserting $$$1$$$. After you finish, reverse the sequence and solve the problem again — that will be the same as inserting $$$x$$$ before $$$1$$$.
Overall complexity: $$$O(n)$$$ per testcase.