CF1420C1 Pokémon Army (easy version)

这是该问题的简单版本。不同之处在于，简单版本没有交换操作。只有在所有版本的问题都被解决后，你才能进行 Hack。 皮卡丘是一只可爱又友善的宝可梦，生活在野生皮卡丘群体中。 但最近众所周知，臭名昭著的火箭队想要偷走所有这些宝可梦！宝可梦训练师 Andrew 决定帮助皮卡丘组建一支宝可梦军队来抵抗。 首先，Andrew 数了数所有的宝可梦——一共有 $n$ 只皮卡丘。第 $i$ 只宝可梦的力量值为 $a_i$，并且这些数都是互不相同的。 作为军队，Andrew 可以选择任意非空子序列的宝可梦。换句话说，Andrew 可以选择一些下标数组 $b$，长度为 $k$，满足 $1 \le b_1 < b_2 < \dots < b_k \le n$，他的军队将由力量值为 $a_{b_1}, a_{b_2}, \dots, a_{b_k}$ 的宝可梦组成。 军队的力量值等于该子序列元素的交错和，即 $a_{b_1} - a_{b_2} + a_{b_3} - a_{b_4} + \dots$。 Andrew 正在尝试调整宝可梦的顺序。他会进行 $q$ 次操作。在第 $i$ 次操作中，Andrew 会交换第 $l_i$ 只和第 $r_i$ 只宝可梦的位置。 注意：本题中 $q=0$。 Andrew 想知道，在初始宝可梦排列下，他能获得的军队最大力量值是多少。他还需要知道每次操作后能获得的最大力量值。 请帮助 Andrew 和宝可梦，否则火箭队就要得逞了！

每个测试点包含多组测试数据。 第一行包含一个正整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 3 \cdot 10^5, q = 0$），分别表示宝可梦的数量和操作次数。 第二行包含 $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$。

对于每个测试用例，输出 $q+1$ 个整数：分别表示交换前和每次交换后军队的最大力量值。

在第三个测试用例中，我们可以这样组建军队：\[1\ 2\ 5\ 4\ 3\ 6\ 7\]，其力量值为 $5-3+7=9$。 由 ChatGPT 4.1 翻译