P17521 [ECUSTPC 2026 Fall] 天外来物

> *在燥热的季节，一颗流星划过天际，留下光亮的拖尾。* > > *我循着光奔跑的那个夜晚，便是故事的开端。*

有 $n$ 颗水晶，从左到右编号为 $1$ 到 $n$ 。第 $i$ 颗水晶初始时含有 $a_i$ 单位的能量。你可以按照任意顺序依次采集这 $n$ 颗水晶。 当你采集编号为 $i$ 的水晶时： - 你获得该水晶当前所含的能量值，并累加到总得分中。 - 如果 $i > 1$ 且编号为 $i - 1$ 的水晶还未被采集，它的能量值会变成其当前能量的相反数。 - 如果 $i < n$ 且编号为 $i + 1$ 的水晶还未被采集，它的能量值会变成其当前能量的相反数。 注意，水晶的编号不会随采集发生变化。 采集完所有 $n$ 颗水晶后，可能的最大总得分是多少？

第一行输入一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的数量。 每组测试数据第一行输入一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示水晶的数量。 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$)，表示每颗水晶初始的能量值。 保证所有测试数据的 $\sum n \le 2 \times 10^5$。

对于每组测试数据，输出一行一个整数，表示可能的最大总得分。

### 样例 1 解释 对于第 1 组测试数据，按照编号 $3 \to 5\to 1\to 2\to 4$ 的顺序采集可以使得最大得分达到 $15$ 。可以证明这是最大值。