CF1420C2.Pokémon Army (hard version)

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 \lt b_2 \lt \dots \lt 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!

这是该问题的困难版本。两个版本的区别在于，简单版本中没有交换操作。只有当该问题的所有版本均被解决时，才允许进行 hack。

皮卡丘是一种可爱又友善的宝可梦，生活在野生皮卡丘群落中。

但最近人们得知，臭名昭著的火箭队企图偷走所有这些宝可梦！训练家安德鲁决定帮助皮卡丘组建一支宝可梦军队来抵抗。

首先，安德鲁清点了所有宝可梦——恰好有 $n$ 只皮卡丘。第 $i$ 只皮卡丘的力量值为 $a_i$，且所有这些数值互不相同。

作为一支军队，安德鲁可以任选一个非空的宝可梦子序列。换言之，安德鲁从 $k$ 个下标中选出一个数组 $b$，满足 $1 \le b_1 \lt b_2 \lt \dots \lt b_k \le n$，他的军队将由力量值分别为 $a_{b_1}, a_{b_2}, \dots, a_{b_k}$ 的宝可梦组成。

军队的强度定义为该子序列元素的交错和（alternating sum），即 $a_{b_1} - a_{b_2} + a_{b_3} - a_{b_4} + \dots$。

安德鲁正在对宝可梦的排列顺序进行实验。他执行 $q$ 次操作；在第 $i$ 次操作中，安德鲁交换第 $l_i$ 只与第 $r_i$ 只宝可梦的位置。

安德鲁希望知道：在初始宝可梦排列下，他所能获得的军队最大强度是多少；此外，他还希望知道每次操作后所能获得的最大强度。

请帮助安德鲁和宝可梦们吧，否则火箭队将实现他们狡猾的阴谋！

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

每个测试包含多个测试用例。

第一行包含一个正整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 3 \cdot 10^5,\ 0 \le q \le 3 \cdot 10^5$），分别表示宝可梦的数量和操作次数。

第二行包含 $n$ 个互不相同的正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示各宝可梦的战斗力。

接下来的 $q$ 行中，第 $i$ 行包含两个正整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示在第 $i$ 次操作中交换的宝可梦的下标。

保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$，且所有测试用例的 $q$ 之和不超过 $3 \cdot 10^5$。

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

对于每个测试用例，输出 $q+1$ 个整数：交换前军队的最大战斗力，以及每次交换后的最大战斗力。

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

我们来看第三个测试用例：

最初，我们可以这样组建一支军队：[1\ 2\ 5\ 4\ 3\ 6\ 7]，其战力为 $5-3+7=9$。

第一次操作后，我们可以这样组建一支军队：[2\ 1\ 5\ 4\ 3\ 6\ 7]，其战力为 $2-1+5-3+7=10$。

第二次操作后，我们可以这样组建一支军队：[2\ 1\ 5\ 4\ 3\ 7\ 6]，其战力为 $2-1+5-3+7=10$。

第三次操作后，我们可以这样组建一支军队：[2\ 1\ 4\ 5\ 3\ 7\ 6]，其战力为 $2-1+5-3+7=10$。

第四次操作后，我们可以这样组建一支军队：[1\ 2\ 4\ 5\ 3\ 7\ 6]，其战力为 $5-3+7=9$。

所有操作完成后，我们可以这样组建一支军队：[1\ 4\ 2\ 5\ 3\ 7\ 6]，其战力为 $4-2+5-3+7=11$。