CF2062C.Cirno and Operations

Cirno 有一个长度为 $n$ 的序列 $a$ 。她可以执行以下两种操作中的任意一种（可能零次），除非当前序列 $a$ 的长度为 $1$：

• 反转序列。严格来说，序列 $[a_1, a_2, \ldots, a_n]$ 变为 $[a_n, a_{n-1}, \ldots, a_1]$。
• 将序列替换为其差分序列。严格来说，序列 $[a_1, a_2, \ldots, a_n]$ 变为 $[a_2 - a_1, a_3 - a_2, \ldots, a_n - a_{n-1}]$。

在所有操作之后，找到序列 $a$ 的元素和的最大值。

输入的第一行包含一个整数 $t (1 \leq t \leq 100 )$ — 输入测试用例的数量。

每个测试用例的第一行包含一个整数 $ n ( 1 \leq n \leq 50 )$ — 序列 $ a $ 的长度。

每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n ( |a_i| \leq 1000 )$ — 序列 $ a $。

对于每个测试用例，输出一个整数，表示序列的元素和的最大值。

在第一个测试用例中，Cirno 无法进行任何操作，因此答案是 $-1000$。

在第二个测试用例中，Cirno 首先反转序列，然后将其替换为差分序列：$[5, -3] \to [-3, 5] \to [8]$。可以证明这样能使总和最大化，因此答案是 $8$。

在第三个测试用例中，Cirno 可以选择不进行任何操作，因此答案是 $1001$。