Let us define the score of an array B (B_{1}, B_{2}, B_{3},...,B_{k}) as:

\begin{equation}
score(B)=\begin{cases}
\sum_{i=1}^{k}B_{i}, & \text{if } k > 1 \text{ and } Max(B) - SecondMax(B) < X.\\
-\sum_{i=1}^{k}B_{i}, & \text{otherwise}.
\end{cases}
\end{equation}

Here, SecondMax(B) denotes the second element in B if we sort it in non-increasing order.

You are given an array A with N elements. You can partition it into multiple continuous subarrays, aiming to maximize the sum of the scores of each of the subarrays. Note that, in a partition, each element of the array belongs to exactly one subarray.

Additionally, you should perform Q queries. For each given value of X, find the maximum sum of score if you partition the array optimally.

------ Input Format ------ 

- The first line contains T - the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and Q - the size of the array A and the number of queries.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.
- The third line contains Q space-separated integers X_{1}, X_{2}, \ldots, X_{Q}.

------ Output Format ------ 

For each test case, output Q space-separated integers in a new line, the maximum sum of score you can obtain.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 3\cdot 10^{5}$
$1 ≤ A_{i},X_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $3\cdot 10^{5}$.
- Sum of $Q$ over all test cases does not exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
2
5 3
1 4 3 6 2
1 4 2
5 2
5 7 10 1 1
2 3
----- Sample Output 1 ------ 
-16 16 0 
-20 4
----- explanation 1 ------ 
Test case $1$: In the third query of the first testcase, an optimal partition is $[1, 4, 3], [6, 2]$. The sum of score is $(1 + 4 + 3) - (6 + 2) = 0$.

Test case $2$: In the second query of the second testcase, an optimal partition is $[5, 7], [10], [1, 1]$. The sum of score is $(5 + 7) - (10) + (1 + 1) = 4$.

Difficulty: VERY_HARD
Tags: Graph algorithms

Data structures

Graph traversal
Skill types: Data structures

Starter code:

Solutions:
from collections import Counter, defaultdict, deque
import itertools
import re
import math
from functools import reduce
import operator
import bisect
from heapq import *
import functools
mod = 998244353
import sys
input = sys.stdin.readline

def Cartesian_Tree(a):
	n = len(a)
	g = [[] for _ in range(n)]
	p = [-1] * n
	st = []
	for i in range(n):
		prv = -1
		while st and a[i] > a[st[-1]]:
			prv = st.pop()
		if prv != -1:
			p[prv] = i
		if st:
			p[i] = st[-1]
		st.append(i)
	root = -1
	for i in range(n):
		if p[i] != -1:
			g[p[i]].append(i)
		else:
			root = i
	return (g, root)
INF = 1 << 31
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	sa = sum(a)
	x = list(map(int, input().split()))
	(g, root) = Cartesian_Tree(a)
	xx = sorted(x)
	ans = [0] * (q + 1)
	go = deque([[root, q]])
	while go:
		(now, midx) = go.pop()
		if len(g[now]) == 2:
			dif = a[now] - max(a[g[now][0]], a[g[now][1]])
			idx = bisect.bisect_right(xx, dif)
			if idx > 0:
				ans[0] -= 2 * a[now]
				ans[min(midx, idx)] += 2 * a[now]
			midx = min(midx, idx)
		elif len(g[now]) == 1:
			dif = a[now] - a[g[now][0]]
			idx = bisect.bisect_right(xx, dif)
			if idx > 0:
				ans[0] -= 2 * a[now]
				ans[min(midx, idx)] += 2 * a[now]
			midx = min(midx, idx)
		else:
			ans[0] -= 2 * a[now]
			ans[midx] += 2 * a[now]
		for i in g[now]:
			go.append([i, midx])
	for i in range(1, q):
		ans[i] += ans[i - 1]
	for i in range(q):
		ans[i] += sa
	rans = [0] * q
	for i in range(q):
		idx = bisect.bisect_right(xx, x[i])
		rans[i] = ans[idx - 1]
	print(*rans)


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(5 * 10 ** 5)
inp = lambda : list(map(int, input().split()))

class segtree:

	def __init__(self, n, function, bound):
		self.st = [bound] * (2 * n)
		self.size = n
		self.function = function
		self.bound = bound

	def update(self, x, value):
		x += self.size
		self.st[x] = value
		while x > 1:
			x >>= 1
			self.st[x] = self.function(self.st[2 * x], self.st[2 * x + 1])

	def query(self, x, y):
		x += self.size
		y += self.size + 1
		ans = self.bound
		while x < y:
			if x & 1:
				ans = self.function(ans, self.st[x])
				x += 1
			if y & 1:
				y -= 1
				ans = self.function(ans, self.st[y])
			x //= 2
			y //= 2
		return ans

def dfs(left, right, mx):
	if left > right:
		return
	if left == right:
		(l, h) = (0, q - 1)
		index = 0
		while l <= h:
			mid = (l + h) // 2
			if queries[mid][0] <= mx:
				index = mid + 1
				l = mid + 1
			else:
				h = mid - 1
		sub[index] += 2 * a[left]
		return
	mval = st.query(left, right)
	(l, h) = (0, len(key[mval]) - 1)
	while l <= h:
		mid = (l + h) // 2
		if key[mval][mid] < left:
			l = mid + 1
			continue
		if key[mval][mid] > right:
			h = mid - 1
			continue
		ind = key[mval][mid]
		break
	smval = max(st.query(left, ind - 1), st.query(ind + 1, right))
	mx = min(mx, mval - smval)
	(l, h) = (0, q - 1)
	index = 0
	while l <= h:
		mid = (l + h) // 2
		if queries[mid][0] <= mx:
			index = mid + 1
			l = mid + 1
		else:
			h = mid - 1
	sub[index] += 2 * mval
	dfs(left, ind - 1, mx)
	dfs(ind + 1, right, mx)

def answer():
	global queries, sub, st, key
	key = dict()
	st = segtree(n, max, 0)
	for i in range(n):
		st.update(i, a[i])
		try:
			key[a[i]].append(i)
		except:
			key[a[i]] = [i]
	queries = [[x[i], i] for i in range(q)]
	queries.sort()
	sub = [0 for i in range(q + 1)]
	dfs(0, n - 1, float('inf'))
	for i in range(q - 1, 0, -1):
		sub[i] += sub[i + 1]
	ans = [-1 for i in range(q)]
	for i in range(q):
		ans[queries[i][1]] = total - sub[i + 1]
	return ans
for T in range(int(input())):
	(n, q) = inp()
	a = inp()
	x = inp()
	total = sum(a)
	print(*answer())