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

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

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.


-----Examples-----

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
Output
9
15
31
13


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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Complete search

Constructive algorithms


Solutions:
def solve():
	(n, x) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	ans = 0
	prev = arr[0]
	for num in arr[1:]:
		ans += abs(num - prev)
		prev = num
	lowest = min(arr)
	highest = max(arr)
	if lowest > 1:
		ans += min(2 * (lowest - 1), abs(arr[0] - 1), abs(arr[-1] - 1))
	if highest < x:
		ans += min(2 * (x - highest), abs(arr[0] - x), abs(arr[-1] - x))
	print(ans)
for tc in range(int(input())):
	solve()


def task(n, x, a):
	total = 0
	for i in range(n - 1):
		total += abs(a[i] - a[i + 1])
	mn = min(a)
	mx = max(a)
	start = a[0]
	end = a[-1]
	if mn > 1:
		total += min(2 * (mn - 1), abs(start - 1), abs(end - 1))
	if mx < x:
		total += min(2 * (x - mx), abs(x - start), abs(x - end))
	print(total)
t = int(input())
for i in range(0, t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	task(n, x, a)


import sys
input = sys.stdin.readline

def solve():
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	if n <= 2:
		return max(max(arr), x) - 1
	val = 0
	(mi, ma) = (arr[-1], arr[-1])
	for i in range(n - 1):
		val += abs(arr[i] - arr[i + 1])
		mi = min(arr[i], mi)
		ma = max(arr[i], ma)
	ans = val
	if mi > 1:
		ans += min(abs(arr[0] - 1), abs(arr[-1] - 1), 2 * (mi - 1))
	if ma < x:
		ans += min(abs(arr[0] - x), abs(arr[-1] - x), 2 * (x - ma))
	return ans
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, a) = map(int, input().split())
	l = list(map(int, input().split()))
	d = 0
	for i in range(n - 1):
		d = d + abs(l[i + 1] - l[i])
	x = min(l)
	y = max(l)
	if n == 1:
		if l[0] <= a:
			print(a - 1)
		else:
			print(l[0] - 1)
	elif x == y:
		print(max(l[0], a) - 1)
	elif y <= a:
		print(d + min(2 * (x - 1), l[0] - 1, l[-1] - 1) + min(2 * a - 2 * y, a - l[0], a - l[-1]))
	elif a < x:
		best = 2 * y
		for i in range(n - 1):
			best = min(best, l[i] + l[i + 1])
		print(d + min(2 * (x - 1), l[0] - 1, l[-1] - 1))
	else:
		print(d + min(2 * (x - 1), l[0] - 1, l[-1] - 1))


for t in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	sum = 0
	rs = 0
	for i in range(n - 1):
		rs += abs(a[i + 1] - a[i])
	(c, d) = (max(a), min(a))
	if x > c:
		rs += min(2 * (x - c), x - a[0], x - a[-1])
	if 1 < d:
		rs += min(2 * (d - 1), a[0] - 1, a[-1] - 1)
	print(rs)


for g in range(int(input())):
	(n, e) = map(int, input().split())
	x = list(map(int, input().split()))
	print(sum((abs(x[i + 1] - x[i]) for i in range(n - 1))) + min(2 * max(e - max(x), 0), max(e - x[0], 0), max(e - x[-1], 0)) + min(2 * (min(x) - 1), x[0] - 1, x[-1] - 1))


for i in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	m1 = min(l)
	m2 = max(l)
	m3 = min(l[0], l[-1])
	m4 = max(l[0], l[-1])
	s = 0
	for j in range(n - 1):
		s += abs(l[j] - l[j + 1])
	if x > m2:
		s += m1 - 1
		s += x - m2
		s += min(m1 - 1, m3 - m1) + min(x - m2, m2 - m4)
	else:
		s += m1 - 1
		s += min(m1 - 1, m3 - m1)
	print(s)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	min_a = min(a)
	max_a = max(a)
	cur_sum = 0
	for theta in range(n - 1):
		cur_sum += abs(a[theta + 1] - a[theta])
	if max_a < x:
		val1 = 2 * (x - max_a)
		val2 = x - a[0]
		val3 = x - a[n - 1]
		cur_sum += min(val1, val2, val3)
	if min_a > 1:
		val1 = 2 * (min_a - 1)
		val2 = a[0] - 1
		val3 = a[n - 1] - 1
		cur_sum += min(val1, val2, val3)
	print(cur_sum)


for _ in range(int(input())):
	(n, x) = map(int, input().strip().split())
	l = list(map(int, input().strip().split()))
	co = 0
	if n == 1:
		co = max(x, l[0]) - 1
	else:
		(a, b) = (min(l), max(l))
		for i in range(1, n):
			co += abs(l[i] - l[i - 1])
		if a > 1:
			co += min(2 * (a - 1), min(l[0], l[-1]) - 1)
		if b < x:
			co += min(x - max(l[0], l[-1]), 2 * (x - b))
	print(co)


for t in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	small = min(a)
	large = max(a)
	ans = 0
	ans += min(abs(a[0] - 1), abs(a[-1] - 1), 2 * abs(small - 1))
	if large < x:
		ans += min(abs(a[0] - x), abs(a[-1] - x), 2 * abs(large - x))
	for i in range(n - 1):
		ans += abs(a[i] - a[i + 1])
	print(ans)


t = int(input())
for _ in range(t):
	(n, x) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	min_a = min(a)
	max_a = max(a)
	result = 0
	for i in range(n - 1):
		result += abs(a[i] - a[i + 1])
	result += min((min_a - 1) * 2, a[0] - 1, a[-1] - 1)
	if x > max_a:
		result += min((x - max_a) * 2, x - a[0], x - a[-1])
	print(result)


for t in range(int(input())):
	(n, x) = map(int, input().split())
	L = list(map(int, input().split()))
	M = max(L)
	m = min(L)
	sum = 0
	if m <= 1 and M >= x:
		L.append(L[-1])
		for i in range(n):
			sum += abs(L[i + 1] - L[i])
	elif m <= 1:
		L.append(L[-1])
		for i in range(n):
			sum += abs(L[i + 1] - L[i])
		sum += min(2 * (x - M), x - L[0], x - L[-1])
	elif M >= x:
		L.append(L[-1])
		for i in range(n):
			sum += abs(L[i + 1] - L[i])
		sum += min(2 * (m - 1), L[0] - 1, L[-1] - 1)
	else:
		L.append(L[-1])
		for i in range(n):
			sum += abs(L[i + 1] - L[i])
		sum += min(2 * (m - 1), L[0] - 1, L[-1] - 1)
		sum += min(2 * (x - M), x - L[0], x - L[-1])
	print(sum)


cases = int(input())
for case in range(cases):
	(n, x) = map(int, input().split())
	nums = list(map(int, input().split()))
	diff = 0
	for i in range(n - 1):
		diff += abs(nums[i] - nums[i + 1])
	min_val = min(nums)
	max_val = max(nums)
	if x > max_val:
		diff += min((x - max_val) * 2, x - max(nums[0], nums[-1]))
	if min_val > 1:
		diff += min((min_val - 1) * 2, min(nums[0], nums[-1]) - 1)
	print(diff)


def main():
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	max_a = max(a)
	min_a = min(a)
	ans_max = max(0, (x - max_a) * 2)
	ans_min = (min_a - 1) * 2
	min_ = a[-1]
	max_ = a[0]
	if a[0] < a[-1]:
		min_ = a[0]
		max_ = a[-1]
	ans_min = min(ans_min, min_ - 1)
	ans_max = min(ans_max, max(0, x - max_))
	ans = ans_max + ans_min
	for i in range(1, n):
		ans += abs(a[i] - a[i - 1])
	print(ans)
for _ in range(int(input())):
	main()


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	L = list(map(int, input().split()))
	m1 = min(L)
	m2 = max(L)
	ans = 0
	for i in range(1, n):
		ans += abs(L[i] - L[i - 1])
	ans += min(2 * (m1 - 1), abs(L[0] - 1), abs(L[-1] - 1))
	if x > m2:
		ans += min(2 * (x - m2), abs(L[0] - x), abs(L[-1] - x))
	print(ans)


t = int(input())
for j in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	ce = min((x - max(a)) * 2, x - a[0], x - a[-1])
	pe = min((min(a) - 1) * 2, a[0] - 1, a[-1] - 1)
	if ce < 0:
		ce = 0
	extra = pe + ce
	cost = 0
	for i in range(len(a) - 1):
		cost += abs(a[i] - a[i + 1])
	cost += extra
	print(cost)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	A = [int(k) for k in input().split()]
	a = min(A)
	b = max(A)
	d = 0
	for k in range(1, n):
		d += abs(A[k] - A[k - 1])
	C = 0
	B = 0
	if a > 1:
		C = min(abs(A[0] - 1), abs(A[-1] - 1))
		C = min(C, 2 * abs(a - 1))
	if b < x:
		B = min(abs(A[0] - x), abs(A[-1] - x))
		B = min(B, 2 * abs(b - x))
	print(d + C + B)


if True:
	t = int(input())
	for _ in range(t):
		(n, x) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		if a[0] > a[-1]:
			a.reverse()
		s = 0
		for i in range(n - 1):
			s += abs(a[i] - a[i + 1])
		min_a = min(a)
		max_a = max(a)
		min_x = 1
		max_x = x
		rl = [min(min_x, min_a), min(max_x, min_a)]
		rh = [max(min_x, max_a), max(max_x, max_a)]
		if rl[0] != min_a:
			if (min_a - rl[0]) * 2 < a[0] - rl[0]:
				s += (min_a - rl[0]) * 2
			else:
				s += a[0] - rl[0]
		if rh[1] != max_a:
			if (rh[1] - max_a) * 2 < rh[1] - a[-1]:
				s += (rh[1] - max_a) * 2
			else:
				s += rh[1] - a[-1]
		print(s)


N = int(input())
for _ in range(N):
	(n, m) = input().split(' ')
	nums = input().split(' ')
	(n, m) = (int(n), int(m))
	nums = [int(x) for x in nums]
	ans = 0
	_min = min(nums)
	_max = max(nums)
	for i in range(1, n):
		ans += abs(nums[i] - nums[i - 1])
	if 1 < _min:
		ans += min(nums[0] - 1, nums[-1] - 1, 2 * (_min - 1))
	if m > _max:
		ans += min(m - nums[0], m - nums[-1], 2 * (m - _max))
	print(ans)


T = int(input())
for cid in range(T):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	(mn, mx) = (min(A), max(A))
	a = 2 * (mn - 1)
	b = max(0, 2 * (X - mx))
	F = min(a + b, a + min(abs(X - A[0]), abs(X - A[-1])), b + min(abs(1 - A[0]), abs(1 - A[-1])), abs(1 - A[0]) + abs(X - A[-1]), abs(X - A[0]) + abs(1 - A[-1]))
	for i in range(N - 1):
		F += abs(A[i + 1] - A[i])
	print(F)


for time in range(int(input())):
	(n, x) = map(int, input().split())
	nums = list(map(int, input().split()))
	if n == 1:
		print(max(x - 1, nums[0] - 1, x - nums[0]))
		continue
	s = 0
	mini = float('inf')
	maxi = 0
	for j in range(n - 1):
		s += abs(nums[j] - nums[j + 1])
		if nums[j] > maxi:
			maxi = nums[j]
		if nums[j] < mini:
			mini = nums[j]
	if nums[-1] > maxi:
		maxi = nums[-1]
	if nums[-1] < mini:
		mini = nums[-1]
	if x > maxi:
		option1 = 2 * (x - maxi)
		option2 = x - nums[0]
		option3 = x - nums[-1]
		s += min(option1, option2, option3)
	if 1 < mini:
		option1 = 2 * (mini - 1)
		option2 = nums[0] - 1
		option3 = nums[-1] - 1
		s += min(option1, option2, option3)
	print(s)


import queue
kkkk = int(input())
for _ in range(kkkk):
	(n, x) = map(int, input().split())
	if n == 1:
		a = [int(input())]
	else:
		a = list(map(int, input().split()))
	if n == 1:
		print(max(x, a[0]) - 1)
		continue
	maxn = a[0]
	minn = a[0]
	maxx = 0
	minx = 0
	for i in range(len(a)):
		if a[i] > maxn:
			maxn = a[i]
			maxx = i
		if a[i] < minn:
			minn = a[i]
			minx = i
	ans = 0
	if maxn < x:
		ans += min(min(abs(x - a[0]), abs(x - a[n - 1])), 2 * (x - maxn))
	if minn > 1:
		ans += min(min(abs(1 - a[0]), abs(1 - a[n - 1])), 2 * (minn - 1))
	for i in range(n - 1):
		ans += abs(a[i + 1] - a[i])
	print(ans)


T = int(input())
for t in range(T):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	(mi, ma, c, p1, p2) = (a[0], a[0], 0, 1, 1)
	for i in range(1, n):
		c += abs(a[i] - a[i - 1])
		mi = min(mi, a[i])
		ma = max(ma, a[i])
	if mi == a[0] or mi == a[n - 1]:
		p1 = 0
	if ma == a[0] or ma == a[n - 1]:
		p2 = 0
	if mi > 1:
		c += min((mi - 1) * (p1 + 1), min(a[0], a[n - 1]) - 1)
	if ma < x:
		c += min((x - ma) * (p2 + 1), x - max(a[0], a[n - 1]))
	print(c)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	(dif, mini, maxi) = (0, a[0], a[0])
	for i in range(n - 1):
		dif += abs(a[i] - a[i + 1])
		mini = min(mini, a[i + 1])
		maxi = max(maxi, a[i + 1])
	dif += min(mini * 2 - 2, a[0] - 1, a[-1] - 1)
	if x > maxi:
		dif += min(x * 2 - maxi * 2, x - a[0], x - a[-1])
	print(dif)


t = int(input())
while t > 0:
	p = input().split()
	(n, x) = (int(p[0]), int(p[1]))
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	(ma, mi) = (max(a), min(a))
	ans = 0
	r = 10 ** 7
	s = 10 ** 7
	f1 = 0
	f2 = 0
	for i in range(n):
		if a[i] == ma and x > ma and (i == 0 or i == n - 1):
			f1 = 1
		if a[i] == mi and 1 < mi and (i == 0 or i == n - 1):
			f2 = 1
	(p, m) = (0, 0)
	if ma < x:
		if f1 == 1:
			p = abs(ma - x)
		else:
			p = 2 * abs(ma - x)
	if mi > 1:
		if f2 == 1:
			m = abs(mi - 1)
		else:
			m = 2 * abs(mi - 1)
	for i in range(n):
		if i == 0 or i == n - 1:
			p = min(p, abs(x - a[i]))
			m = min(m, abs(1 - a[i]))
	for i in range(n - 1):
		ans += abs(a[i] - a[i + 1])
	ans += p + m
	print(ans)
	t -= 1


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n - 1):
		ans += abs(a[i] - a[i + 1])
	(mn, mx) = (min(a), max(a))
	if mn == 1 and mx >= k:
		print(ans)
		return
	if mn > 1:
		res = min(a[0] - 1, a[-1] - 1)
		for i in range(n - 1):
			res = min(res, a[i] + a[i + 1] - 2 - abs(a[i] - a[i + 1]))
		ans += res
	if k > mx:
		res = min(k - a[0], k - a[-1])
		for i in range(n - 1):
			res = min(res, 2 * k - a[i] - a[i + 1] - abs(a[i] - a[i + 1]))
		ans += res
	print(ans)
for _ in range(int(input())):
	solve()


import sys
input = sys.stdin.readline

def solve():
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	(mi, ma) = (min(arr), max(arr))
	if n <= 2:
		return max(ma, x) - 1
	val = 0
	for i in range(n - 1):
		val += abs(arr[i] - arr[i + 1])
	if mi <= 1 <= x <= ma:
		return val
	else:
		ans = float('inf')
		for i in range(2):
			if i == 1:
				arr = arr[::-1]
			ans = min(ans, val + x - 1 + abs(arr[0] - x), val + x - 1 + abs(arr[-1] - 1))
			for i in range(n - 1):
				ans = min(ans, val - abs(arr[i + 1] - arr[i]) + x - 1 + abs(1 - arr[i]) + abs(x - arr[i + 1]))
			cost = []
			c = float('inf')
			for i in range(n):
				if i == 0:
					c = min(c, abs(arr[0] - 1))
				else:
					c = min(c, -abs(arr[i] - arr[i - 1]) + abs(arr[i - 1] - 1) + abs(arr[i] - 1))
				cost.append(c)
			f = float('inf')
			for i in range(n):
				if i == n - 1:
					f = min(f, abs(arr[i] - x))
				else:
					f = min(f, -abs(arr[i + 1] - arr[i]) + abs(arr[i] - x) + abs(arr[i + 1] - x))
				ans = min(ans, val + f + cost[i])
		return ans
for _ in range(int(input())):
	print(solve())


t = int(input())
while t:
	t -= 1
	(n, x) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	ans = int(1e+18)
	cur = 0
	for i in range(0, len(l) - 1):
		cur += abs(l[i] - l[i + 1])
	for i in range(2):
		mn = abs(l[0] - 1)
		ans = min(ans, cur + (x - 1) + abs(l[0] - x))
		for i in range(len(l) - 1):
			ans = min(ans, cur + abs(l[i] - 1) + abs(l[i + 1] - x) + (x - 1) - abs(l[i] - l[i + 1]))
			ans = min(ans, cur + mn + abs(l[i + 1] - x) + abs(l[i] - x) - abs(l[i] - l[i + 1]))
			mn = min(mn, abs(l[i] - 1) + abs(l[i + 1] - 1) - abs(l[i] - l[i + 1]))
		ans = min(ans, cur + mn + abs(l[-1] - x))
		l = l[::-1]
	print(ans)