思路与结论

关键观察： 令 $d(i,j)$ 表示位置 $i$ 到初始黑点 $j$ 的距离（在一条线上即为 $|i-j|$）。每一轮“先红再黑”的传播会把颜色层层向外推进一格。可以用归纳得到最终稳定状态：

• 距离 $d(i,j)$ 为 偶数 的位置最终为黑色；
• 距离 $d(i,j)$ 为 奇数 的位置最终为红色。

于是最终的黑色集合恰好是与 $j$ 同奇偶 的全部位置。换言之，无论 $j$ 选在哪个与它同奇偶的具体下标，最终黑色位置集合都 只取决于奇偶性，与 $j$ 的具体值无关。

因此答案就是二选一：

题目内容

小苯有n 个数字排成一排，一开始所有数字都是白色，现在他会将其中恰好一个数字$a_j(1≦j≦n)$染黑，在染黑后，会发生以下事件，直到数组中不存在白色数字。

• 所有和黑色数字相邻的数字都会被染红。
• 所有和红色数字相邻的数字都会被染黑。

小苯想知道，最优情况下，所有黑色数字的总和可以达到多少，请你帮他算一算吧。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≦T≦100)$代表数据组数，每组测试数据描述如下:

第一行一个正整数$n(1≦n≦2×10^5)$,表示数字的个数。

第二行$n$个正整数$a(1≦a_i≦10^9)$,表示每个数字的值。

(保证所有测试数据中，$n$的总和不超过$2×10^5$)

输出描述

对于每组测试数据:

在单独的一行输出一个正整数表示黑色数字的最大总和

样例1

输入

2
5
1 3 3 4 2
4
1 1 1 1

输出

7
2

说明

对于第一组测试数据，我们一开始可以选择$j=2$,将$a_2$染黑，最终黑色数字为:$a_2$和$a_4$,总和为$7$最大。