宝可梦军队（困难版）

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的排列 $a$。你可以选择任意非空子序列 $a_{b_1},a_{b_2},\ldots,a_{b_k}$，其中 $1\le b_1<b_2<\cdots<b_k\le n$。这个子序列的力量为

你需要先求出初始排列能得到的最大力量。随后有 $q$ 次操作，每次交换位置 $l_i$ 与 $r_i$ 上的元素；每次交换后也要求出当前排列能得到的最大力量。

输入格式

第一行包含测试用例数 $t$。

每个测试用例的第一行包含两个整数 $n,q$。

第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$，它们构成 $1$ 到 $n$ 的一个排列。

接下来 $q$ 行，每行包含两个整数 $l_i,r_i$，表示交换这两个位置上的元素。

输出格式

对于每个测试用例，依次输出初始状态以及每次交换后的最大力量，共输出 $q+1$ 个整数，每个整数占一行。

样例输入 1

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

样例输出 1

3
4
2
2
2
9
10
10
10
9
11

数据范围

对于所有数据，$1\le t\le10^3$，$1\le n\le3\times10^5$，$0\le q\le3\times10^5$，$1\le l_i\le r_i\le n$。所有测试用例的 $n$ 之和不超过 $3\times10^5$，$q$ 之和也不超过 $3\times10^5$。