There are $n$ children standing in a line, where the niceness of the $i$-th child is $a_i$. Santa is deciding which children belong on the nice list and which belong on the naughty list.

An integer $X$ is initially set to $0$. Santa will perform the following operation exactly $n-1$ times:

• Choose the first or second child in line and remove them from the line.
• Let $w$ be the niceness of the chosen child.
  • If the first child was chosen, add them to the nice list and add $w$ to $X$.
  • If the second child was chosen, add them to the naughty list and subtract $w$ from $X$.

Note that after all operations, exactly one child remains unassigned to a list.

Determine the maximum possible value of $X$ that Santa can obtain after all $n-1$ operations.

有 $n$ 个孩子站成一排，其中第 $i$ 个孩子的“善良值”为 $a_i$。圣诞老人需要决定哪些孩子列入“善良名单”，哪些列入“顽皮名单”。

初始时，整数 $X$ 设为 $0$。圣诞老人将恰好执行以下操作 $n-1$ 次：

• 选择队列中第一个或第二个孩子，并将其从队列中移除；
• 设被选中孩子的善良值为 $w$：
  • 若选择的是第一个孩子，则将其加入善良名单，并将 $w$ 加到 $X$ 上；
  • 若选择的是第二个孩子，则将其加入顽皮名单，并将 $w$ 从 $X$ 中减去。

注意：经过全部 $n-1$ 次操作后，恰好剩下一个孩子未被分配到任一名单中。

求圣诞老人在完成全部 $n-1$ 次操作后所能得到的 $X$ 的最大可能值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le 2\cdot 10^5$) — the number of children.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9\le a_i\le 10^9$) — the niceness of each child.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\le n\le 2\cdot 10^5$）——儿童的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^9\le a_i\le 10^9$）——每个儿童的“善良值”。

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

For each test case, print a single integer — the maximum possible value of $X$ that Santa can obtain after all $n-1$ operations.

对于每个测试用例，输出一个整数——圣诞老人在执行完全部 $n-1$ 次操作后所能得到的最大可能的 $X$ 值。

In the first test case, Santa will perform exactly one operation. If he chooses the first child, he will add $a_1=2$ to $X$ to get $X=2$; if he chooses the second child, he will subtract $a_2=-3$ from $X$ to get $X=3$. Thus, the answer is $3$.

In the second test case, it is optimal to select the first child in all three operations. The value of $X$ will be $1+4+3=8$.

In the third test case, below is an optimal sequence of operations:

Type

Niceness of remaining children

$X$ after operation

0

—

$[-4, 2, 3, -6]$

$0$

1

First

$[2, 3, -6]$

$-4$

2

First

$[3, -6]$

$-2$

3

Second

$[3]$

$4$

In the fourth test case, below is an optimal sequence of operations:

Type

Niceness of remaining children

$X$ after operation

0

—

$[-2, -3, 4, 10, -9]$

$0$

1

Second

$[-2, 4, 10, -9]$

$3$

2

First

$[4, 10, -9]$

$1$

3

First

$[10, -9]$

$5$

4

First

$[-9]$

$15$

在第一个测试用例中，圣诞老人将恰好执行一次操作。如果他选择第一个孩子，则将 $a_1=2$ 加到 $X$ 上，得到 $X=2$；如果他选择第二个孩子，则从 $X$ 中减去 $a_2=-3$，得到 $X=3$。因此，答案为 $3$。

在第二个测试用例中，最优策略是在全部三次操作中均选择第一个孩子。此时 $X$ 的值为 $1+4+3=8$。

在第三个测试用例中，以下是一个最优的操作序列：

操作类型

剩余孩子的“善良值”

操作后的 $X$

0

—

$[-4, 2, 3, -6]$

$0$

1

第一种

$[2, 3, -6]$

$-4$

2

第一种

$[3, -6]$

$-2$

3

第二种

$[3]$

$4$

在第四个测试用例中，以下是一个最优的操作序列：

操作类型

剩余孩子的“善良值”

操作后的 $X$

0

—

$[-2, -3, 4, 10, -9]$

$0$

1

第二种

$[-2, 4, 10, -9]$

$3$

2

第一种

$[4, 10, -9]$

$1$

3

第一种

$[10, -9]$

$5$

4

第一种

$[-9]$

$15$