This is the hard version of the problem. The difference between the versions is that the easy version has no swap operations. You can make hacks only if all versions of the problem are solved.

Pikachu is a cute and friendly pokémon living in the wild pikachu herd.

But it has become known recently that infamous team R wanted to steal all these pokémon! Pokémon trainer Andrew decided to help Pikachu to build a pokémon army to resist.

First, Andrew counted all the pokémon — there were exactly $n$ pikachu. The strength of the $i$-th pokémon is equal to $a_i$, and all these numbers are distinct.

As an army, Andrew can choose any non-empty subsequence of pokemons. In other words, Andrew chooses some array $b$ from $k$ indices such that $1 \le b_1 < b_2 < \dots < b_k \le n$, and his army will consist of pokémons with forces $a_{b_1}, a_{b_2}, \dots, a_{b_k}$.

The strength of the army is equal to the alternating sum of elements of the subsequence; that is, $a_{b_1} - a_{b_2} + a_{b_3} - a_{b_4} + \dots$.

Andrew is experimenting with pokémon order. He performs $q$ operations. In $i$-th operation Andrew swaps $l_i$-th and $r_i$-th pokémon.

Andrew wants to know the maximal stregth of the army he can achieve with the initial pokémon placement. He also needs to know the maximal strength after each operation.

Help Andrew and the pokémon, or team R will realize their tricky plan!


-----Input-----

Each test contains multiple test cases.

The first line contains one positive integer $t$ ($1 \le t \le 10^3$) denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1 \le n \le 3 \cdot 10^5, 0 \le q \le 3 \cdot 10^5$) denoting the number of pokémon and number of operations respectively.

The second line contains $n$ distinct positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) denoting the strengths of the pokémon.

$i$-th of the last $q$ lines contains two positive integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) denoting the indices of pokémon that were swapped in the $i$-th operation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$, and the sum of $q$ over all test cases does not exceed $3 \cdot 10^5$. 


-----Output-----

For each test case, print $q+1$ integers: the maximal strength of army before the swaps and after each swap.


-----Example-----
Input
3
3 1
1 3 2
1 2
2 2
1 2
1 2
1 2
7 5
1 2 5 4 3 6 7
1 2
6 7
3 4
1 2
2 3

Output
3
4
2
2
2
9
10
10
10
9
11



-----Note-----

Let's look at the third test case:

Initially we can build an army in such way: [1 2 5 4 3 6 7], its strength will be $5-3+7=9$.

After first operation we can build an army in such way: [2 1 5 4 3 6 7], its strength will be $2-1+5-3+7=10$.

After second operation we can build an army in such way: [2 1 5 4 3 7 6], its strength will be $2-1+5-3+7=10$.

After third operation we can build an army in such way: [2 1 4 5 3 7 6], its strength will be $2-1+5-3+7=10$.

After forth operation we can build an army in such way: [1 2 4 5 3 7 6], its strength will be $5-3+7=9$.

After all operations we can build an army in such way: [1 4 2 5 3 7 6], its strength will be $4-2+5-3+7=11$.

Difficulty: HARD
Tags: Implementation

Greedy algorithms

Dynamic programming

Divide and conquer

Data structures
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
input = __import__('sys').stdin.readline

def check(*inds):
	global localmax, localmin, maxs, mins
	for ind in inds:
		if not ok(ind):
			continue
		if localmax[ind] == 0 and s[ind - 1] < s[ind] > s[ind + 1]:
			localmax[ind] = 1
			maxs += s[ind]
		if localmin[ind] == 0 and s[ind - 1] > s[ind] < s[ind + 1]:
			localmin[ind] = 1
			mins += s[ind]

def upd0(*inds):
	global localmax, localmin, maxs, mins
	for ind in inds:
		if not ok(ind):
			continue
		if localmax[ind]:
			localmax[ind] = 0
			maxs -= s[ind]
		if localmin[ind]:
			localmin[ind] = 0
			mins -= s[ind]

def ok(ind):
	return 0 <= ind - 1 <= ind + 1 <= n
ans = []
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	n += 1
	s = [0] + list(map(int, input().split())) + [0]
	localmax = [0] * n
	localmin = [0] * n
	maxs = mins = 0
	for i in range(n):
		check(i)
	ans.append(maxs - mins)
	for _ in range(q):
		(l, r) = map(int, input().split())
		upd0(l, l - 1, l + 1, r, r - 1, r + 1)
		(s[l], s[r]) = (s[r], s[l])
		check(l, l - 1, l + 1, r, r - 1, r + 1)
		ans.append(maxs - mins)
print(*ans, sep='\n')


import os
import sys
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
GANS = []

def print(*args):
	global GANS
	for i in args:
		GANS.append(f'{i}'.encode())
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	li = [-1] + [int(i) for i in input().split()] + [-1]
	if n == 1:
		print(li[1])
		for qi in range(q):
			trash = input()
			print(li[1])
		continue
	if n == 2:
		print(max(li[2], li[1]))
		for qi in range(q):
			trash = input()
			print(max(li[2], li[1]))
		continue
	hi = li[0]
	status = 1
	lo = li[0]
	ans = 0
	for i in li[1:]:
		if status:
			if i > hi:
				hi = i
			else:
				status = 0
				lo = i
		elif i < lo:
			lo = i
		else:
			status = 1
			ans += hi - lo
			hi = i
	ans += hi
	print(ans)
	for qi in range(q):
		(u, v) = map(int, input().split())
		if u == v:
			print(ans)
			continue
		da = max(li[u - 1], li[u + 1])
		xiao = min(li[u - 1], li[u + 1])
		ans -= max(li[u] - da, 0)
		ans -= max(xiao - li[u], 0)
		ans += max(li[v] - da, 0)
		ans += max(xiao - li[v], 0)
		tmp = li[u]
		li[u] = li[v]
		da = max(li[v - 1], li[v + 1])
		xiao = min(li[v - 1], li[v + 1])
		ans -= max(li[v] - da, 0)
		ans -= max(xiao - li[v], 0)
		ans += max(tmp - da, 0)
		ans += max(xiao - tmp, 0)
		li[v] = tmp
		print(ans)
os.write(1, b'\n'.join(GANS) + b'\n')


import sys, os
import math
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def MI():
	return map(int, input().split())

def out(var):
	sys.stdout.write(str(var) + '\n')
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split())) + [0]
	out = 0
	for i in range(n):
		out += max(arr[i] - arr[i - 1], 0)
	print(out)
	for i in range(q):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		out -= max(arr[b + 1] - arr[b], 0)
		out -= max(arr[b] - arr[b - 1], 0)
		if b != a + 1:
			out -= max(arr[a + 1] - arr[a], 0)
		out -= max(arr[a] - arr[a - 1], 0)
		(arr[a], arr[b]) = (arr[b], arr[a])
		out += max(arr[b + 1] - arr[b], 0)
		out += max(arr[b] - arr[b - 1], 0)
		if b != a + 1:
			out += max(arr[a + 1] - arr[a], 0)
		out += max(arr[a] - arr[a - 1], 0)
		print(out)


import sys
input = lambda : sys.stdin.readline().rstrip()
ANS = []
T = int(input())
for _ in range(T):
	(N, Q) = list(map(int, input().split()))
	A = [int(a) for a in input().split()]
	ans = sum((max(b - a, 0) for (a, b) in zip([0] + A, A)))
	ANS.append(ans)
	for _ in range(Q):
		(l, r) = list(map(int, input().split()))
		(l, r) = (l - 1, r - 1)
		if l == r:
			ANS.append(ans)
			continue
		ans -= max(A[l] - A[l - 1], 0) if l else A[l]
		if l < N - 1:
			ans -= max(A[l + 1] - A[l], 0)
		if r > l + 1:
			ans -= max(A[r] - A[r - 1], 0)
		if r < N - 1:
			ans -= max(A[r + 1] - A[r], 0)
		(A[l], A[r]) = (A[r], A[l])
		ans += max(A[l] - A[l - 1], 0) if l else A[l]
		if l < N - 1:
			ans += max(A[l + 1] - A[l], 0)
		if r > l + 1:
			ans += max(A[r] - A[r - 1], 0)
		if r < N - 1:
			ans += max(A[r + 1] - A[r], 0)
		ANS.append(ans)
print('\n'.join(map(str, ANS)))


import sys
import math
import collections
import bisect
import itertools
import decimal
import copy
import heapq
INF = 10 ** 20
MOD = 998244353
ni = lambda : int(sys.stdin.readline())
ns = lambda : map(int, sys.stdin.readline().split())
na = lambda : list(map(int, sys.stdin.readline().split()))
na1 = lambda : list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
flush = lambda : sys.stdout.flush()

def main():
	t = ni()
	for _ in range(t):
		(n, q) = ns()
		a = [-INF] + na() + [-INF]
		ans = 0
		for i in range(1, n + 1):
			if a[i - 1] < a[i] and a[i] > a[i + 1]:
				ans += a[i]
			elif a[i - 1] > a[i] and a[i] < a[i + 1]:
				ans -= a[i]
		print(ans)
		for _ in range(q):
			(l, r) = ns()
			for li in range(l - 2, l + 3):
				if 1 <= li <= n:
					if a[li - 1] < a[li] and a[li] > a[li + 1]:
						ans -= a[li]
					elif a[li - 1] > a[li] and a[li] < a[li + 1]:
						ans += a[li]
			for ri in range(max(l + 3, r - 2), r + 3):
				if 1 <= ri <= n:
					if a[ri - 1] < a[ri] and a[ri] > a[ri + 1]:
						ans -= a[ri]
					elif a[ri - 1] > a[ri] and a[ri] < a[ri + 1]:
						ans += a[ri]
			(a[l], a[r]) = (a[r], a[l])
			for li in range(l - 2, l + 3):
				if 1 <= li <= n:
					if a[li - 1] < a[li] and a[li] > a[li + 1]:
						ans += a[li]
					elif a[li - 1] > a[li] and a[li] < a[li + 1]:
						ans -= a[li]
			for ri in range(max(l + 3, r - 2), r + 3):
				if 1 <= ri <= n:
					if a[ri - 1] < a[ri] and a[ri] > a[ri + 1]:
						ans += a[ri]
					elif a[ri - 1] > a[ri] and a[ri] < a[ri + 1]:
						ans -= a[ri]
			print(ans)
main()


import sys
inp = sys.stdin.buffer.readline
inar = lambda : list(map(int, inp().split()))
inin = lambda : int(inp())
inst = lambda : inp().decode().strip()

def wrl(*args):
	for _arg in args:
		sys.stdout.write(str(_arg) + ' ')
	sys.stdout.write('\n')
from math import log2
_T_ = inin()
for _t_ in range(_T_):
	(n, q) = inar()
	a = [0] + inar() + [0]
	diff = []
	for i in range(n + 1):
		diff.append(max(0, a[i + 1] - a[i]))
	print(sum(diff))
	ans = sum(diff)
	for qq in range(q):
		(l, r) = inar()
		al = a[l]
		ar = a[r]
		a[l] = ar
		ans -= diff[l - 1]
		ans -= diff[l]
		diff[l - 1] = max(0, a[l] - a[l - 1])
		diff[l] = max(0, a[l + 1] - a[l])
		ans += diff[l - 1]
		ans += diff[l]
		a[r] = al
		ans -= diff[r - 1]
		ans -= diff[r]
		diff[r - 1] = max(0, a[r] - a[r - 1])
		diff[r] = max(0, a[r + 1] - a[r])
		ans += diff[r - 1]
		ans += diff[r]
		print(ans)


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	(n, q) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	total = 0
	last = 0
	for i in range(n):
		total += max(arr[i] - last, 0)
		last = arr[i]
	arr = [0] + arr + [arr[-1]]
	print(total)
	ans = []
	for _ in range(q):
		(x, y) = list(map(int, input().split()))
		(x_new, y_new) = (arr[y], arr[x])
		(j1, j2) = (max(arr[x] - arr[x - 1], 0), max(arr[x + 1] - arr[x], 0))
		arr[x] = x_new
		arr[-1] = arr[-2]
		(n1, n2) = (max(arr[x] - arr[x - 1], 0), max(arr[x + 1] - arr[x], 0))
		total -= j1 + j2
		total += n1 + n2
		(j1, j2) = (max(arr[y] - arr[y - 1], 0), max(arr[y + 1] - arr[y], 0))
		arr[y] = y_new
		arr[-1] = arr[-2]
		(n1, n2) = (max(arr[y] - arr[y - 1], 0), max(arr[y + 1] - arr[y], 0))
		total -= j1 + j2
		total += n1 + n2
		ans.append(str(total))
	print(*ans, sep='\n')


import sys
input = sys.stdin.readline

def main():
	(n, q) = map(int, input().split())
	alst = [0, 0] + list(map(int, input().split())) + [0, 0]
	pm = [0 for _ in range(n + 4)]
	ans = 0
	for i in range(2, n + 2):
		if alst[i - 1] < alst[i] and alst[i + 1] <= alst[i]:
			pm[i] = 1
			ans += alst[i]
		elif alst[i - 1] > alst[i] and alst[i + 1] >= alst[i]:
			pm[i] = -1
			ans -= alst[i]
	print(ans)
	for _ in range(q):
		(l, r) = map(int, input().split())
		l += 1
		r += 1
		lr_s = set()
		for lr in [l, r]:
			for i in range(lr - 1, lr + 2):
				lr_s.add(i)
		for i in lr_s:
			ans -= alst[i] * pm[i]
		(alst[l], alst[r]) = (alst[r], alst[l])
		for i in lr_s:
			if alst[i - 1] < alst[i] and alst[i + 1] <= alst[i]:
				pm[i] = 1
				ans += alst[i]
			elif alst[i - 1] > alst[i] and alst[i + 1] >= alst[i]:
				pm[i] = -1
				ans -= alst[i]
			else:
				pm[i] = 0
		print(ans)
for _ in range(int(input())):
	main()


from sys import stdin, stdout
input = stdin.readline
c = 0
a = []
b = []

def f(i):
	if a[i] == 0:
		return 0
	if a[i - 1] < a[i] > a[i + 1]:
		return 1
	if a[i - 1] > a[i] < a[i + 1]:
		return -1
	return 0

def relax(i):
	global c
	c += (f(i) - b[i]) * a[i]
	b[i] = f(i)

def relax1(i):
	global c
	c -= b[i] * a[i]
	b[i] = 0
for _ in range(int(input())):
	c = 0
	(n, q) = map(int, input().split())
	(*a,) = map(int, input().split())
	a = [0] + a + [0]
	b = [0] * (n + 2)
	for i in range(1, n + 1):
		relax(i)
	print(c)
	for i in range(q):
		(l, r) = map(int, input().split())
		relax1(l)
		relax1(l - 1)
		relax1(l + 1)
		relax1(r)
		relax1(r - 1)
		relax1(r + 1)
		(a[l], a[r]) = (a[r], a[l])
		relax(l)
		relax(l - 1)
		relax(l + 1)
		relax(r)
		relax(r - 1)
		relax(r + 1)
		print(c)


import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
import io
import os
input = sys.stdin.readline
import random
mo = 10 ** 9 + 7

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())
for _ in range(inin()):
	(n, k) = cin()
	l = ain()
	ans = 0
	if n <= 2:
		ans = max(l)
	else:
		for i in range(n):
			if i == 0:
				if l[i + 1] < l[i]:
					ans += l[0]
			elif i == n - 1:
				if l[i - 1] < l[i]:
					ans += l[i]
			elif l[i - 1] < l[i] and l[i + 1] < l[i]:
				ans += l[i]
			elif l[i - 1] > l[i] and l[i + 1] > l[i]:
				ans -= l[i]
	print(ans)
	for j in range(k):
		(a, b) = cin()
		if n <= 2:
			ans = ans
		else:
			(a, b) = (a - 1, b - 1)
			for i in range(max(a - 2, 0), min(a + 3, n)):
				if i == 0:
					if l[i + 1] < l[i]:
						ans -= l[0]
				elif i == n - 1:
					if l[i - 1] < l[i]:
						ans -= l[i]
				elif l[i - 1] < l[i] and l[i + 1] < l[i]:
					ans -= l[i]
				elif l[i - 1] > l[i] and l[i + 1] > l[i]:
					ans += l[i]
			for i in range(max(b - 2, a + 3), min(b + 3, n)):
				if i == 0:
					if l[i + 1] < l[i]:
						ans -= l[0]
				elif i == n - 1:
					if l[i - 1] < l[i]:
						ans -= l[i]
				elif l[i - 1] < l[i] and l[i + 1] < l[i]:
					ans -= l[i]
				elif l[i - 1] > l[i] and l[i + 1] > l[i]:
					ans += l[i]
			(l[b], l[a]) = (l[a], l[b])
			for i in range(max(a - 2, 0), min(a + 3, n)):
				if i == 0:
					if l[i + 1] < l[i]:
						ans += l[0]
				elif i == n - 1:
					if l[i - 1] < l[i]:
						ans += l[i]
				elif l[i - 1] < l[i] and l[i + 1] < l[i]:
					ans += l[i]
				elif l[i - 1] > l[i] and l[i + 1] > l[i]:
					ans -= l[i]
			for i in range(max(b - 2, a + 3), min(b + 3, n)):
				if i == 0:
					if l[i + 1] < l[i]:
						ans += l[0]
				elif i == n - 1:
					if l[i - 1] < l[i]:
						ans += l[i]
				elif l[i - 1] < l[i] and l[i + 1] < l[i]:
					ans += l[i]
				elif l[i - 1] > l[i] and l[i + 1] > l[i]:
					ans -= l[i]
		print(ans)


def isLocalMin(i, a, n):
	if a[i - 1] > a[i] < a[i + 1]:
		return True
	else:
		return False

def isLocalMax(i, a, n):
	if a[i - 1] < a[i] > a[i + 1]:
		return True
	else:
		return False

def main():
	t = int(input())
	ans = []
	for _ in range(t):
		(n, q) = readIntArr()
		a = readIntArr()
		a = [-1] + a + [-1]
		swaps = []
		for __ in range(q):
			swaps.append(readIntArr())
		total = 0
		for i in range(1, n + 1):
			if isLocalMin(i, a, n):
				total -= a[i]
			elif isLocalMax(i, a, n):
				total += a[i]
		ans.append(total)
		for (l, r) in swaps:
			idxes = set()
			for ll in range(l - 1, l + 2):
				if 1 <= ll < n + 1:
					idxes.add(ll)
			for rr in range(r - 1, r + 2):
				if 1 <= rr < n + 1:
					idxes.add(rr)
			for idx in idxes:
				if isLocalMin(idx, a, n):
					total += a[idx]
				elif isLocalMax(idx, a, n):
					total -= a[idx]
			(a[l], a[r]) = (a[r], a[l])
			for idx in idxes:
				if isLocalMin(idx, a, n):
					total -= a[idx]
				elif isLocalMax(idx, a, n):
					total += a[idx]
			ans.append(total)
	multiLineArrayPrint(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]
main()


import os, sys
from io import BytesIO, IOBase

def op(x, a, dp, ans, n):
	if x < 0 or x >= n:
		return ans
	fl = -1 if x and a[x] < a[x - 1] else 1
	fl1 = -1 if x != n - 1 and a[x] < a[x + 1] else 1
	if fl == 1 and fl1 == 1:
		dp[x] = 1
	elif fl == -1 and fl1 == -1:
		dp[x] = -1
	else:
		dp[x] = 0
	if (not x or x == n - 1) and dp[x] == -1:
		dp[x] = 0
	ans += dp[x] * a[x]
	return ans

def main():
	for _ in range(int(input())):
		(n, q) = map(int, input().split())
		a = list(map(int, input().split()))
		if n != 1:
			dp = [1 if a[0] > a[1] else 0] + [0] * (n - 2) + [1 if a[-1] > a[-2] else 0]
			for i in range(1, n - 1):
				if a[i] < a[i + 1] and a[i] < a[i - 1]:
					dp[i] = -1
				elif a[i] > a[i + 1] and a[i] > a[i - 1]:
					dp[i] = 1
		else:
			dp = [1]
		ans = 0
		for i in range(n):
			ans += dp[i] * a[i]
		print(ans)
		for _ in range(q):
			(l, r) = map(lambda xx: int(xx) - 1, input().split())
			y = {l - 1, l, l + 1, r - 1, r, r + 1}
			for i in y:
				if i < 0 or i >= n:
					continue
				ans -= a[i] * dp[i]
			(a[l], a[r]) = (a[r], a[l])
			for x in y:
				ans = op(x, a, dp, ans, n)
			print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
GANS = []

def print(*args):
	global GANS
	for i in args:
		GANS.append(f'{i}'.encode())
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	li = [-1] + [int(i) for i in input().split()] + [-1]
	if n == 1:
		print(li[1])
		for qi in range(q):
			trash = input()
			print(li[1])
		continue
	if n == 2:
		print(max(li[2], li[1]))
		for qi in range(q):
			trash = input()
			print(max(li[2], li[1]))
		continue
	hi = li[0]
	status = 1
	lo = li[0]
	ans = 0
	for i in li[1:]:
		if status:
			if i > hi:
				hi = i
			else:
				status = 0
				lo = i
		elif i < lo:
			lo = i
		else:
			status = 1
			ans += hi - lo
			hi = i
	ans += hi
	print(ans)
	for qi in range(q):
		(u, v) = map(int, input().split())
		if u == v:
			print(ans)
			continue
		da = max(li[u - 1], li[u + 1])
		xiao = min(li[u - 1], li[u + 1])
		ans -= max(li[u] - da, 0)
		ans -= max(xiao - li[u], 0)
		ans += max(li[v] - da, 0)
		ans += max(xiao - li[v], 0)
		tmp = li[u]
		li[u] = li[v]
		da = max(li[v - 1], li[v + 1])
		xiao = min(li[v - 1], li[v + 1])
		ans -= max(li[v] - da, 0)
		ans -= max(xiao - li[v], 0)
		ans += max(tmp - da, 0)
		ans += max(xiao - tmp, 0)
		li[v] = tmp
		print(ans)
os.write(1, b'\n'.join(GANS) + b'\n')


import io
import os

def solve(N, Q, A, LR):
	deltas = [max(A[i] - A[i + 1], 0) for i in range(N - 1)]
	total = sum(deltas)
	ans = []
	ans.append(str(total + A[-1]).encode())
	for (l, r) in LR:
		l -= 1
		r -= 1
		(A[l], A[r]) = (A[r], A[l])
		for i in [l - 1, l, r - 1, r]:
			if 0 <= i < N - 1:
				delta = max(A[i] - A[i + 1], 0)
				oldDelta = deltas[i]
				if delta != oldDelta:
					deltas[i] = delta
					total += delta - oldDelta
		ans.append(str(total + A[-1]).encode())
	assert len(ans) == Q + 1
	return b'\n'.join(ans) + b'\n'
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N, Q) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	LR = [[int(x) for x in input().split()] for i in range(Q)]
	ans = solve(N, Q, A, LR)
	os.write(1, ans)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import sys
from sys import stdin, stdout
input = stdin.readline

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
c = 0
a = []
b = []

def f(i):
	if a[i] == 0:
		return 0
	if a[i - 1] < a[i] > a[i + 1]:
		return 1
	if a[i - 1] > a[i] < a[i + 1]:
		return -1
	return 0

def relax(i):
	global c
	c += (f(i) - b[i]) * a[i]
	b[i] = f(i)

def relax1(i):
	global c
	c -= b[i] * a[i]
	b[i] = 0
for _ in range(int(input())):
	c = 0
	(n, q) = map(int, input().split())
	(*a,) = map(int, input().split())
	a = [0] + a + [0]
	b = [0] * (n + 2)
	for i in range(1, n + 1):
		relax(i)
	print(c)
	for i in range(q):
		(l, r) = map(int, input().split())
		relax1(l)
		relax1(l - 1)
		relax1(l + 1)
		relax1(r)
		relax1(r - 1)
		relax1(r + 1)
		(a[l], a[r]) = (a[r], a[l])
		relax(l)
		relax(l - 1)
		relax(l + 1)
		relax(r)
		relax(r - 1)
		relax(r + 1)
		print(c)


import sys

def main():
	iter_data = map(int, sys.stdin.read().split())
	t = next(iter_data)
	for t_it in range(t):
		(n, q) = (next(iter_data), next(iter_data))
		a = [0] + [next(iter_data) for _ in range(n)] + [0]
		all_ans = [0] * (q + 1)
		val = [0] * (n + 1)
		for i in range(n + 1):
			val[i] = max(a[i], a[i + 1])
		cur_ans = sum(val) - sum(a)
		all_ans[0] = cur_ans
		for q_it in range(1, q + 1):
			(l, r) = (next(iter_data), next(iter_data))
			if l != r:
				(a[l], a[r]) = (a[r], a[l])
				cur_ans -= val[l - 1] + val[l] + val[r]
				val[l - 1] = max(a[l - 1], a[l])
				val[l] = max(a[l], a[l + 1])
				val[r] = max(a[r], a[r + 1])
				cur_ans += val[l - 1] + val[l] + val[r]
				if r - l > 1:
					cur_ans -= val[r - 1]
					val[r - 1] = max(a[r - 1], a[r])
					cur_ans += val[r - 1]
			all_ans[q_it] = cur_ans
		print(*all_ans, sep='\n')
main()


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=300006, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += 1
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += 1
		self.temp.data = pre_xor

	def query(self, xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = xor & 1 << i
			if not val:
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				elif self.temp.right:
					self.temp = self.temp.right
			elif self.temp.right and self.temp.right.count > 0:
				self.temp = self.temp.right
			elif self.temp.left:
				self.temp = self.temp.left
			self.temp.count -= 1
		return xor ^ self.temp.data
for ik in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	if n == 1:
		print(l[0])
		for i in range(q):
			(a, b) = map(int, input().split())
			print(l[0])
		continue
	ans = 0
	for i in range(n):
		if i == 0:
			if l[i] > l[i + 1]:
				ans += l[i]
		elif i == n - 1:
			if l[i] > l[i - 1]:
				ans += l[i]
		elif l[i] > l[i - 1] and l[i] > l[i + 1]:
			ans += l[i]
		elif l[i] < l[i - 1] and l[i] < l[i + 1]:
			ans -= l[i]
	print(ans)

	def remove(i, ans):
		if i == 0:
			if l[i] > l[i + 1]:
				ans -= l[i]
		elif i == n - 1:
			if l[i] > l[i - 1]:
				ans -= l[i]
		elif l[i] > l[i - 1] and l[i] > l[i + 1]:
			ans -= l[i]
		elif l[i] < l[i - 1] and l[i] < l[i + 1]:
			ans += l[i]
		return ans

	def add(i, ans):
		if i == 0:
			if l[i] > l[i + 1]:
				ans += l[i]
		elif i == n - 1:
			if l[i] > l[i - 1]:
				ans += l[i]
		elif l[i] > l[i - 1] and l[i] > l[i + 1]:
			ans += l[i]
		elif l[i] < l[i - 1] and l[i] < l[i + 1]:
			ans -= l[i]
		return ans
	for j in range(q):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		ind = set()
		if a != 0:
			ind.add(a - 1)
		if a != n - 1:
			ind.add(a + 1)
		ind.add(a)
		if b != 0:
			ind.add(b - 1)
		if b != n - 1:
			ind.add(b + 1)
		ind.add(b)
		for i in ind:
			ans = remove(i, ans)
		(l[a], l[b]) = (l[b], l[a])
		for i in ind:
			ans = add(i, ans)
		print(ans)


from sys import stdin
from math import log2

def readline():
	return stdin.readline()

def findsum(a):
	sm = 0
	for i in range(len(a)):
		if isMax(a, i):
			sm += a[i]
		elif isMin(a, i):
			sm -= a[i]
	return sm

def isMax(a, i):
	return i != 0 and i != len(a) - 1 and (a[i - 1] < a[i] > a[i + 1])

def isMin(a, i):
	return i != 0 and i != len(a) - 1 and (a[i - 1] > a[i] < a[i + 1])

def change(a, i1, i2, s):
	used = set()
	for j in [i1, i2]:
		for i in range(j - 1, j + 2):
			if i not in used:
				if isMax(a, i):
					s -= a[i]
					used.add(i)
				if isMin(a, i):
					s += a[i]
					used.add(i)
	(a[i1], a[i2]) = (a[i2], a[i1])
	used = set()
	for j in [i1, i2]:
		for i in range(j - 1, j + 2):
			if i not in used:
				if isMax(a, i):
					s += a[i]
					used.add(i)
				if isMin(a, i):
					s -= a[i]
					used.add(i)
	return s
tests = int(readline())
res = []
for t in range(0, tests):
	(n, q) = map(int, readline().split())
	a = [0, *list(map(int, readline().rstrip('\n').split(' '))), 0]
	s = findsum(a)
	res.append(str(s))
	for i in range(q):
		(i1, i2) = map(int, readline().split())
		s = change(a, i1, i2, s)
		res.append(str(s))
print(' '.join(res))


from math import inf as _inf
import sys as _sys
_NEGATIVE_INFINITY = -_inf

def main():
	t = int(input())
	for i_t in range(t):
		(n, q) = _read_ints()
		a = tuple(_read_ints())
		swaps = (_read_ints() for i_q in range(q))
		swaps = ((l - 1, r - 1) for (l, r) in swaps)
		results = find_max_army_powers_after_swaps(a, swaps)
		print(*results, sep='\n')

def _read_line():
	result = _sys.stdin.readline()
	assert result[-1] == '\n'
	return result[:-1]

def _read_ints():
	return map(int, _read_line().split(' '))

def find_max_army_powers_after_swaps(units_powers, swaps):
	units_powers = list(units_powers)
	units_powers = 2 * [_NEGATIVE_INFINITY] + units_powers + 2 * [_NEGATIVE_INFINITY]
	result = sum((_find_contribution(x1, x2, x3) for (x1, x2, x3) in zip(units_powers, units_powers[1:], units_powers[2:])))
	yield result
	for (i_a, i_b) in swaps:
		i_a += 2
		i_b += 2
		indices_may_be_affected = list({i_a - 1, i_a, i_a + 1, i_b - 1, i_b, i_b + 1})
		contribution_before = 0
		for i in indices_may_be_affected:
			contribution_before += _find_contribution(units_powers[i - 1], units_powers[i], units_powers[i + 1])
		(units_powers[i_a], units_powers[i_b]) = (units_powers[i_b], units_powers[i_a])
		contribution_after = 0
		for i in indices_may_be_affected:
			contribution_after += _find_contribution(units_powers[i - 1], units_powers[i], units_powers[i + 1])
		result -= contribution_before
		result += contribution_after
		yield result

def _find_contribution(x1, x2, x3):
	if x1 < x2 > x3:
		result = x2
	elif x1 > x2 < x3:
		result = -x2
	else:
		result = 0
	return result
main()


from sys import stdin
tt = int(stdin.readline())
pls = []
for loop in range(tt):
	(n, q) = list(map(int, stdin.readline().split()))
	a = list(map(int, stdin.readline().split()))
	a = [0] + a + [0]
	lis = [0] * len(a)
	ans = 0
	for i in range(1, len(a) - 1):
		if a[i - 1] < a[i] and a[i] > a[i + 1]:
			lis[i] = 1
			ans += a[i]
		elif a[i - 1] > a[i] and a[i] < a[i + 1]:
			lis[i] = -1
			ans -= a[i]
	pls.append(ans)
	for loop in range(q):
		(l, r) = list(map(int, stdin.readline().split()))
		if l == r:
			pls.append(ans)
			continue
		ch = {}
		ch[l - 1] = 0
		ch[l] = 0
		ch[l + 1] = 0
		ch[r - 1] = 0
		ch[r] = 0
		ch[r + 1] = 0
		for i in ch:
			ans -= a[i] * lis[i]
		(a[l], a[r]) = (a[r], a[l])
		for i in ch:
			if i == 0 or i == len(a) - 1:
				pass
			elif a[i - 1] < a[i] and a[i] > a[i + 1]:
				lis[i] = 1
				ans += a[i]
			elif a[i - 1] > a[i] and a[i] < a[i + 1]:
				lis[i] = -1
				ans -= a[i]
			else:
				lis[i] = 0
		pls.append(ans)
print('\n'.join(map(str, pls)))


import sys
input = sys.stdin.buffer.readline
INF = 10 ** 18
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = [-INF] + list(map(int, input().split())) + [-INF]
	queries = [list(map(int, input().split())) for i in range(q)]
	ans = 0
	for i in range(1, n + 1):
		if a[i - 1] < a[i] and a[i + 1] < a[i]:
			ans += a[i]
		if a[i] < a[i - 1] and a[i] < a[i + 1]:
			ans -= a[i]
	print(ans)
	for (ll, rr) in queries:
		for l in range(ll - 2, ll + 3):
			if not (0 <= l - 1 and l + 1 <= n + 1):
				continue
			elif a[l - 1] < a[l] and a[l + 1] < a[l]:
				ans -= a[l]
			elif a[l] < a[l - 1] and a[l] < a[l + 1]:
				ans += a[l]
		for r in range(max(rr - 2, ll + 3), rr + 3):
			if not (0 <= r - 1 and r + 1 <= n + 1):
				continue
			elif a[r - 1] < a[r] and a[r + 1] < a[r]:
				ans -= a[r]
			elif a[r] < a[r - 1] and a[r] < a[r + 1]:
				ans += a[r]
		(a[ll], a[rr]) = (a[rr], a[ll])
		for l in range(ll - 2, ll + 3):
			if not (0 <= l - 1 and l + 1 <= n + 1):
				continue
			elif a[l - 1] < a[l] and a[l + 1] < a[l]:
				ans += a[l]
			elif a[l] < a[l - 1] and a[l] < a[l + 1]:
				ans -= a[l]
		for r in range(max(rr - 2, ll + 3), rr + 3):
			if not (0 <= r - 1 and r + 1 <= n + 1):
				continue
			elif a[r - 1] < a[r] and a[r + 1] < a[r]:
				ans += a[r]
			elif a[r] < a[r - 1] and a[r] < a[r + 1]:
				ans -= a[r]
		print(ans)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

def main():
	t = int(input())
	ans_a = []
	for ti in range(t):
		(n, q) = map(int, input().split())
		a = [-1] + list(map(int, input().split())) + [-1]
		is_peak = [0] * (n + 2)
		score = 0
		for i in range(1, n + 1):
			if a[i - 1] < a[i] > a[i + 1]:
				is_peak[i] = 1
				score += a[i]
			elif a[i - 1] > a[i] < a[i + 1]:
				is_peak[i] = 2
				score -= a[i]
		ans_a.append(str(score))
		for (li, ri) in (map(int, input().split()) for _ in range(q)):
			for (i, new_val) in ((li, a[ri]), (ri, a[li])):
				for j in range(i - 1, i + 2):
					if is_peak[j]:
						score += a[j] * (-1 if is_peak[j] == 1 else 1)
				a[i] = new_val
				for j in range(i - 1, i + 2):
					if 1 <= j <= n and a[j - 1] < a[j] > a[j + 1]:
						is_peak[j] = 1
						score += a[j]
					elif 1 <= j <= n and a[j - 1] > a[j] < a[j + 1]:
						is_peak[j] = 2
						score -= a[j]
					else:
						is_peak[j] = 0
			ans_a.append(str(score))
	output(*ans_a)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
data = [list(map(int, line.split())) for line in sys.stdin.readlines()]
line = 1
for _ in range(data[0][0]):
	(n, q) = data[line]
	a = [0] + data[line + 1] + [0]
	(low, high) = (set(), set())
	s = 0
	for i in range(1, n + 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			high.add(a[i])
			s += a[i]
		elif a[i] < a[i - 1] and a[i] < a[i + 1]:
			low.add(a[i])
			s -= a[i]
	print(s)
	for ii in range(line + 2, line + q + 2):
		(x, y) = data[ii]
		(a[x], a[y]) = (a[y], a[x])
		d = {a[x - 1], a[x], a[x + 1], a[y - 1], a[y], a[y + 1]}
		t = low & d
		s += sum(t)
		low -= t
		t = high & d
		s -= sum(t)
		high -= t
		d = {x - 1, x, x + 1, y - 1, y, y + 1}
		for i in d:
			if 0 < i <= n:
				if a[i] > a[i - 1] and a[i] > a[i + 1]:
					high.add(a[i])
					s += a[i]
				elif a[i] < a[i - 1] and a[i] < a[i + 1]:
					low.add(a[i])
					s -= a[i]
		print(s)
	line += q + 2


import io
import os
z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
o = []
y = lambda a, b: a - b if a - b > 0 else 0
for _ in range(int(z())):
	(n, q) = map(int, z().split())
	p = [0] + [*map(int, z().split())]
	s = m = 0
	for i in p:
		if i > m:
			s += i - m
		m = i
	o.append(s)
	for i in range(q):
		(a, b) = map(int, z().split())
		if a == b:
			o.append(s)
			continue
		(va, vb) = (p[a], p[b])
		va1 = p[a - 1]
		c = b < n
		if c:
			vb1 = p[b + 1]
		(p[a], p[b]) = (vb, va)
		lv = nv = 0
		if b - a < 2:
			if vb > va:
				lv += vb - va
			if va > va1:
				lv += va - va1
			if c and vb1 > vb:
				lv += vb1 - vb
			if va > vb:
				nv += va - vb
			if vb > va1:
				nv += vb - va1
			if c and vb1 > va:
				nv += vb1 - va
		else:
			(va2, vb2) = (p[a + 1], p[b - 1])
			if va2 > va:
				lv += va2 - va
			if va > va1:
				lv += va - va1
			if vb > vb2:
				lv += vb - vb2
			if c and vb1 > vb:
				lv += vb1 - vb
			if va2 > vb:
				nv += va2 - vb
			if vb > va1:
				nv += vb - va1
			if va > vb2:
				nv += va - vb2
			if c and vb1 > va:
				nv += vb1 - va
		s += nv - lv
		o.append(s)
print('\n'.join(map(str, o)))


import sys
inp = sys.stdin.readline
inar = lambda : list(map(int, inp().split()))
inin = lambda : int(inp())
from math import log2
_T_ = inin()
for _t_ in range(_T_):
	(n, q) = inar()
	a = [0] + inar() + [0]
	diff = []
	for i in range(n + 1):
		diff.append(max(0, a[i + 1] - a[i]))
	print(sum(diff))
	ans = sum(diff)
	for qq in range(q):
		(l, r) = inar()
		al = a[l]
		ar = a[r]
		a[l] = ar
		ans -= diff[l - 1]
		ans -= diff[l]
		diff[l - 1] = max(0, a[l] - a[l - 1])
		diff[l] = max(0, a[l + 1] - a[l])
		ans += diff[l - 1]
		ans += diff[l]
		a[r] = al
		ans -= diff[r - 1]
		ans -= diff[r]
		diff[r - 1] = max(0, a[r] - a[r - 1])
		diff[r] = max(0, a[r + 1] - a[r])
		ans += diff[r - 1]
		ans += diff[r]
		print(ans)


import sys

def solve(n, q, a, u):
	z = []

	def chk(i):
		if a[i - 1] < a[i] > a[i + 1]:
			return a[i]
		if a[i - 1] > a[i] < a[i + 1]:
			return -a[i]
		return 0
	if n == 1:
		z.append(a[0])
		for i in u:
			z.append(a[0])
	else:
		a = [-1] + a + [-1]
		c = 0
		for i in range(1, n + 1):
			c += chk(i)
		z.append(c)
		for (l, r) in u:
			if l == r:
				z.append(c)
			else:
				b = {l, max(1, l - 1), min(n, l + 1), r, max(1, r - 1), min(n, r + 1)}
				for j in b:
					c -= chk(j)
				(a[l], a[r]) = (a[r], a[l])
				for j in b:
					c += chk(j)
				z.append(c)
	return z

def stdin():
	while True:
		yield sys.stdin.readline()
inputs = stdin()
t = int(next(inputs))
z = []
for _ in range(t):
	(n, q) = map(int, next(inputs).split())
	a = list(map(int, next(inputs).split()))
	u = [map(int, next(inputs).split()) for i in range(q)]
	z += solve(n, q, a, u)
print('\n'.join(map(str, z)))


import sys

def big(i):
	global a
	return a[i] > a[i - 1] and a[i] >= a[i + 1]

def little(i):
	global a
	return a[i] <= a[i - 1] and a[i] < a[i + 1]

def make(a, i, x):
	global s
	if big(i):
		s -= a[i]
	if little(i):
		s += a[i]
	if big(i - 1):
		s -= a[i - 1]
	if little(i - 1):
		s += a[i - 1]
	if big(i + 1):
		s -= a[i + 1]
	if little(i + 1):
		s += a[i + 1]
	a[i] = x
	if big(i):
		s += a[i]
	if little(i):
		s -= a[i]
	if big(i - 1):
		s += a[i - 1]
	if little(i - 1):
		s -= a[i - 1]
	if big(i + 1):
		s += a[i + 1]
	if little(i + 1):
		s -= a[i + 1]
t = int(input())
for I in range(t):
	(n, q) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	a.append(0)
	a.append(0)
	up = True
	s = 0
	for i in range(n):
		if up:
			if a[i] > a[i - 1]:
				s += a[i] - a[i - 1]
			else:
				up = False
		elif a[i] > a[i - 1]:
			up = True
			s += a[i] - a[i - 1]
	print(s)
	for i in range(q):
		(l, r) = map(int, sys.stdin.readline().split())
		l -= 1
		r -= 1
		ll = a[l]
		rr = a[r]
		make(a, l, rr)
		make(a, r, ll)
		print(s)


import sys, math
import io, os
data = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write('\n'.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
mod = 998244353
INF = float('inf')
ans = []
for t in range(int(data())):
	(n, q) = mdata()
	a = mdata()
	lis = []
	for i in range(1, n):
		lis.append(max(a[i - 1] - a[i], 0))
	s = sum(lis)
	ans.append(s + a[-1])
	for i in range(q):
		(l, r) = mdata()
		(l, r) = (l - 1, r - 1)
		(a[l], a[r]) = (a[r], a[l])
		if l:
			s -= lis[l - 1]
			lis[l - 1] = max(a[l - 1] - a[l], 0)
			s += lis[l - 1]
		if l < n - 1:
			s -= lis[l]
			lis[l] = max(a[l] - a[l + 1], 0)
			s += lis[l]
		if r:
			s -= lis[r - 1]
			lis[r - 1] = max(a[r - 1] - a[r], 0)
			s += lis[r - 1]
		if r < n - 1:
			s -= lis[r]
			lis[r] = max(a[r] - a[r + 1], 0)
			s += lis[r]
		ans.append(s + a[-1])
outl(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	if n > 1:
		m = [0 for i in range(n)]
		k = True
		ans = 0
		for i in range(n):
			if i == 0 and a[i] > a[i + 1]:
				ans += a[i]
				m[i] = 1
				k = False
			elif i == n - 1 and a[i] > a[i - 1] and k:
				ans += a[i]
				m[i] = 1
				k = False
			elif i > 0 and i < n - 1:
				if a[i] > a[i - 1] and a[i] > a[i + 1] and k:
					ans += a[i]
					m[i] = 1
					k = False
				elif a[i] < a[i - 1] and a[i] < a[i + 1] and (not k):
					ans -= a[i]
					m[i] = -1
					k = True
		print(ans)
		out = []
		out.append(ans)
		for i in range(q):
			z = []
			(left, right) = map(int, input().split())
			(a[left - 1], a[right - 1]) = (a[right - 1], a[left - 1])
			(m[left - 1], m[right - 1]) = (m[right - 1], m[left - 1])
			z = [left - 1, right - 1, left, right, left - 2, right - 2]
			for ind in z:
				if ind < 0 or ind >= n:
					continue
				elif ind == 0:
					if a[ind] > a[ind + 1]:
						out[0] += abs(1 - m[ind]) * a[ind]
						m[ind] = 1
					else:
						out[0] += (0 - m[ind]) * a[ind]
						m[ind] = 0
				elif ind == n - 1:
					if a[ind] > a[ind - 1]:
						out[0] += abs(1 - m[ind]) * a[ind]
						m[ind] = 1
					else:
						out[0] += (0 - m[ind]) * a[ind]
						m[ind] = 0
				elif a[ind] > a[ind - 1] and a[ind + 1] < a[ind]:
					out[0] += abs(1 - m[ind]) * a[ind]
					m[ind] = 1
				elif a[ind] < a[ind - 1] and a[ind] < a[ind + 1]:
					out[0] -= abs(-1 - m[ind]) * a[ind]
					m[ind] = -1
				else:
					out[0] += (0 - m[ind]) * a[ind]
					m[ind] = 0
			print(out[0])
	else:
		print(a[0])
		for _ in range(q):
			(left, right) = map(int, input().split())
			print(a[0])


import os
import sys
from io import BytesIO, IOBase
_str = str
BUFSIZE = 8192

def str(x=b''):
	return x if type(x) is bytes else _str(x).encode()

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def inp():
	return sys.stdin.readline()

def mpint():
	return map(int, sys.stdin.readline().split(' '))

def itg():
	return int(sys.stdin.readline())

def solve():
	(n, q) = mpint()
	arr = list(mpint()) + [0]
	ans = 0
	for i in range(n):
		ans += max(0, arr[i] - arr[i - 1])
	print(ans)
	for _ in range(q):
		(lf, rg) = mpint()
		lf -= 1
		rg -= 1
		ans -= max(0, arr[rg + 1] - arr[rg])
		ans -= max(0, arr[rg] - arr[rg - 1])
		if rg != lf + 1:
			ans -= max(0, arr[lf + 1] - arr[lf])
		ans -= max(0, arr[lf] - arr[lf - 1])
		(arr[rg], arr[lf]) = (arr[lf], arr[rg])
		ans += max(0, arr[rg + 1] - arr[rg])
		ans += max(0, arr[rg] - arr[rg - 1])
		if rg != lf + 1:
			ans += max(0, arr[lf + 1] - arr[lf])
		ans += max(0, arr[lf] - arr[lf - 1])
		print(ans)
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
for _ in range(itg()):
	solve()


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def get_ints():
	return map(int, sys.stdin.readline().split())

def get_ints():
	return map(int, sys.stdin.readline().split())
ans = 0

def change(ind, val, arr):
	global ans
	ans -= arr[0]
	if ind > 0:
		ans -= max(0, arr[ind] - arr[ind - 1])
	if ind + 1 < len(arr):
		ans -= max(0, arr[ind + 1] - arr[ind])
	arr[ind] = val
	if ind > 0:
		ans += max(0, arr[ind] - arr[ind - 1])
	if ind + 1 < len(arr):
		ans += max(0, arr[ind + 1] - arr[ind])
	ans += arr[0]
for _ in range(int(input())):
	(n, q) = get_ints()
	ans = 0
	arr = [0] * n
	ans = 0
	i = 0
	for ii in input().split():
		change(i, int(ii), arr)
		i += 1
	A = []
	A.append(ans)
	for i in range(q):
		(a, b) = get_ints()
		a -= 1
		b -= 1
		temp = arr[a]
		change(a, arr[b], arr)
		change(b, temp, arr)
		A.append(ans)
	for iii in A:
		print(iii)


import bisect
import array
import functools
import math
input = __import__('sys').stdin.readline

def solve():
	(n, Q) = map(int, input().split())
	a = array.array('i', map(int, input().split()))

	def jud(x):
		if x < 0 or x >= n:
			return 0
		(p, s) = (0, 0)
		if x != 0:
			p = a[x - 1]
		if x + 1 != n:
			s = a[x + 1]
		if p < a[x] and s <= a[x]:
			return a[x]
		if p > a[x] and s >= a[x]:
			return -a[x]
		return 0
	ans = 0
	for i in range(n):
		ans = ans + jud(i)
	print(ans)
	for i in range(Q):
		(x, y) = map(int, input().split())
		(kx, ky) = (a[x - 1], a[y - 1])
		ans = ans - jud(x - 2) - jud(x - 1) - jud(x)
		a[x - 1] = ky
		ans = ans + jud(x - 2) + jud(x - 1) + jud(x)
		ans = ans - jud(y - 2) - jud(y - 1) - jud(y)
		a[y - 1] = kx
		ans = ans + jud(y - 2) + jud(y - 1) + jud(y)
		print(ans)
T = int(input())
for Tid in range(T):
	solve()


import sys
import array
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = array.array('i', [-1] + list(map(int, input().split())) + [-1])

	def f(i):
		if i <= 0 or i >= n + 1:
			return 0
		if a[i - 1] < a[i] > a[i + 1]:
			return a[i]
		if a[i - 1] > a[i] < a[i + 1]:
			return -a[i]
		return 0
	ans = 0
	for i in range(n):
		ans += f(i + 1)
	print(ans)
	for __ in range(q):
		(l, r) = map(int, input().split())
		(u, v) = (a[l], a[r])
		ans -= f(l - 1) + f(l) + f(l + 1)
		a[l] = v
		ans += f(l - 1) + f(l) + f(l + 1)
		ans -= f(r - 1) + f(r) + f(r + 1)
		a[r] = u
		ans += f(r - 1) + f(r) + f(r + 1)
		print(ans)


import io
import os
from collections import Counter, defaultdict, deque

class FenwickTree:

	def __init__(self, x):
		self.bit = x
		for i in range(len(x)):
			j = i | i + 1
			if j < len(x):
				x[j] += x[i]

	def update(self, idx, x):
		while idx < len(self.bit):
			self.bit[idx] += x
			idx |= idx + 1

	def query(self, end):
		x = 0
		while end:
			x += self.bit[end - 1]
			end &= end - 1
		return x

	def findkth(self, k):
		idx = -1
		for d in reversed(range(len(self.bit).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(self.bit) and k >= self.bit[right_idx]:
				idx = right_idx
				k -= self.bit[idx]
		return idx + 1

def solve(N, Q, A, LR):
	deltas = [max(A[i] - A[i + 1], 0) for i in range(N - 1)]
	segTree = FenwickTree(list(deltas))
	ans = []
	ans.append(str(segTree.query(N - 1) + A[-1]).encode())
	for (l, r) in LR:
		l -= 1
		r -= 1
		(A[l], A[r]) = (A[r], A[l])
		for i in [l - 1, l, r - 1, r]:
			if 0 <= i < N - 1:
				delta = max(A[i] - A[i + 1], 0)
				oldDelta = deltas[i]
				if delta != oldDelta:
					deltas[i] = delta
					segTree.update(i, delta - oldDelta)
		ans.append(str(segTree.query(N - 1) + A[-1]).encode())
	assert len(ans) == Q + 1
	return b'\n'.join(ans) + b'\n'
DEBUG = False
if DEBUG:
	import random
	random.seed(0)
	for _ in range(1):
		N = random.randint(1, 3 * 10 ** 5)
		Q = random.randint(1, 3 * 10 ** 5)
		A = [random.randint(1, N) for i in range(N)]
		LR = [[random.randint(1, N), random.randint(1, N)] for i in range(Q)]
		print('tc', _, N, Q)
		ans1 = solve(N, Q, A, LR)
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N, Q) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	LR = [[int(x) for x in input().split()] for i in range(Q)]
	ans = solve(N, Q, A, LR)
	os.write(1, ans)


import sys
z = sys.stdin.readline
o = []
y = lambda a, b: a - b if a - b > 0 else 0
for _ in range(int(z())):
	(n, q) = map(int, z().split())
	p = [0] + [*map(int, z().split())]
	s = m = 0
	for i in p:
		if i > m:
			s += i - m
		m = i
	o.append(s)
	for i in range(q):
		(a, b) = map(int, z().split())
		if a == b:
			o.append(s)
			continue
		(va, vb) = (p[a], p[b])
		va1 = p[a - 1]
		c = b < n
		if c:
			vb1 = p[b + 1]
		(p[a], p[b]) = (vb, va)
		lv = nv = 0
		if b - a < 2:
			if vb > va:
				lv += vb - va
			if va > va1:
				lv += va - va1
			if c and vb1 > vb:
				lv += vb1 - vb
			if va > vb:
				nv += va - vb
			if vb > va1:
				nv += vb - va1
			if c and vb1 > va:
				nv += vb1 - va
		else:
			(va2, vb2) = (p[a + 1], p[b - 1])
			if va2 > va:
				lv += va2 - va
			if va > va1:
				lv += va - va1
			if vb > vb2:
				lv += vb - vb2
			if c and vb1 > vb:
				lv += vb1 - vb
			if va2 > vb:
				nv += va2 - vb
			if vb > va1:
				nv += vb - va1
			if va > vb2:
				nv += va - vb2
			if c and vb1 > va:
				nv += vb1 - va
		s += nv - lv
		o.append(s)
print('\n'.join(map(str, o)))


import itertools
import math
import sys
from collections import defaultdict

def stdinWrapper():
	data = '3\n3 1\n1 3 2\n1 2\n2 2\n1 2\n1 2\n1 2\n7 5\n1 2 5 4 3 6 7\n1 2\n6 7\n3 4\n1 2\n2 3\n\n'
	for line in data.split('\n'):
		yield line
if '--debug' not in sys.argv:

	def stdinWrapper():
		while True:
			yield sys.stdin.readline()
inputs = stdinWrapper()

def inputWrapper():
	return next(inputs)

def getType(_type):
	return _type(inputWrapper())

def getArray(_type):
	return [_type(x) for x in inputWrapper().split()]

def solve(a, queries):
	results = []
	res = 0
	a = [-1] + a + [-1]

	def check(res, i, remove=False):
		k = 1
		if remove:
			k = -1
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			return res + a[i] * k
		elif a[i] < a[i - 1] and a[i] < a[i + 1]:
			return res - a[i] * k
		return res
	for i in range(1, len(a) - 1):
		res = check(res, i)
	results.append(res)
	for (l, r) in queries:
		affected = {l, r, max(1, l - 1), max(1, r - 1), min(len(a) - 2, l + 1), min(len(a) - 2, r + 1)}
		for x in affected:
			res = check(res, x, True)
		tmp = a[l]
		a[l] = a[r]
		a[r] = tmp
		for x in affected:
			res = check(res, x)
		results.append(res)
	return results
t = getType(int)
for _ in range(t):
	(n, q) = getArray(int)
	a = getArray(int)
	queries = [getArray(int) for _ in range(q)]
	res = solve(a, queries)
	print('\n'.join([str(x) for x in res]))


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
c = 0
a = []
b = []

def f(i):
	if a[i] == 0:
		return 0
	if a[i - 1] < a[i] > a[i + 1]:
		return 1
	if a[i - 1] > a[i] < a[i + 1]:
		return -1
	return 0

def relax(i):
	global c
	c += (f(i) - b[i]) * a[i]
	b[i] = f(i)

def relax1(i):
	global c
	c -= b[i] * a[i]
	b[i] = 0
for _ in range(int(input())):
	c = 0
	(n, q) = map(int, input().split())
	(*a,) = map(int, input().split())
	a = [0] + a + [0]
	b = [0] * (n + 2)
	for i in range(1, n + 1):
		relax(i)
	print(c)
	for i in range(q):
		(l, r) = map(int, input().split())
		relax1(l)
		relax1(l - 1)
		relax1(l + 1)
		relax1(r)
		relax1(r - 1)
		relax1(r + 1)
		(a[l], a[r]) = (a[r], a[l])
		relax(l)
		relax(l - 1)
		relax(l + 1)
		relax(r)
		relax(r - 1)
		relax(r + 1)
		print(c)