题目描述

小苯有一个长度为 $n$ 的数组 $a$ ，数组中可能存在负数使总和不够大。小苯可通过以下两种操作任意次（两种操作都可任意使用）来使数组 $a$ 的总和（即$\{a_{1}+a_{2}+\cdots +a_{n}\}$ ）尽可能大：

• 选择两个相邻数字 $a_{i}$ 和 $a_{i + 1}$（$1 \leq i < |a|$ ），将其删除，其余数字顺序拼接。操作后数组 $a$ 变为 $\{a_{1}, a_{2}, \cdots, a_{i - 1}, a_{i + 2}, \cdots, a_{n}\}$ 。
• 选择三个连续数字 $a_{i}$、$a_{i + 1}$ 和 $a_{i + 2}$（$1 \leq i < |a| - 1$ ），将其删除，其余数字顺序拼接。操作后数组 $a$ 变为 $\{a_{1}, a_{2}, \cdots, a_{i - 1}, a_{i + 3}, \cdots, a_{n}\}$ 。 请计算数组 $a$ 经过操作后能达到的最大总和。

输入格式

• 第一行：一个正整数 $T$（$1 \leq T \leq 100$ ），表示数据组数。
• 接下来 $T$ 组数据，每组数据格式如下：
  • 第一行：一个正整数 $n$（$1 \leq n \leq 2\times10^{5}$ ），表示数组 $a$ 的初始长度。
  • 第二行：$n$ 个整数 $a_{i}$（$-10^{9} \leq a_{i} \leq 10^{9}$ ），表示数组 $a$ 。
  • 保证所有测试数据中，$n$ 的总和不超过 $2\times10^{5}$ 。

输出格式

对于每组测试数据，在单独的一行输出一个整数，表示数组 $a$ 的最大总和。

输入输出样例 #1

• 输入 #1

2
12
1 3 -2 -1 -4 -1 -2 5 -4 15 -10 9
5
1 2 3 4 5

• 输出 #1

20
15

• 解释 #1 对于第一组测试数据，通过合理使用两种操作，最终得到数组 $\{1, 3, 5, -4, 15\}$ ，此时数组总和为 $20$ 最大。 对于第二组测试数据，不进行操作时数组总和最大，为 $15$ 。