A15005 | $Insert a Progression$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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'$ ?

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

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.

输入 #1

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

输出 #1

C++ 编辑器

输入

输出