CF1420C1.Pokémon Army (easy version)

This is the easy 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.

Note: $q=0$ in this version of the task.

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$ 只宝可梦的位置。

注意：在此版本的任务中，$q = 0$。

安德鲁希望知道，在初始宝可梦排列下，他所能达到的最大军队力量值。此外，他还需知道每次操作后所能达到的最大军队力量值。

请帮助安德鲁和皮卡丘们吧，否则火箭队将实现他们险恶的阴谋！

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, q = 0$) 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,\ 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$。

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

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

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

在第三个测试用例中，我们可以按如下方式组建军队：[1\ 2\ 5\ 4\ 3\ 6\ 7]，其战力为 $5−3+7=9$。