思路与结论
关键观察： 令 d(i,j) 表示位置 i 到初始黑点 j 的距离（在一条线上即为 ∣i−j∣）。每一轮“先红再黑”的传播会把颜色层层向外推进一格。可以用归纳得到最终稳定状态：
- 距离 d(i,j) 为 偶数 的位置最终为黑色；
- 距离 d(i,j) 为 奇数 的位置最终为红色。
于是最终的黑色集合恰好是与 j 同奇偶 的全部位置。换言之，无论 j 选在哪个与它同奇偶的具体下标，最终黑色位置集合都 只取决于奇偶性，与 j 的具体值无关。
P3727.第1题-小苯的数字染色
题目内容
小苯有n 个数字排成一排，一开始所有数字都是白色，现在他会将其中恰好一个数字aj(1≦j≦n)染黑，在染黑后，会发生以下事件，直到数组中不存在白色数字。
- 所有和黑色数字相邻的数字都会被染红。
- 所有和红色数字相邻的数字都会被染黑。
小苯想知道，最优情况下，所有黑色数字的总和可以达到多少，请你帮他算一算吧。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≦T≦100)代表数据组数，每组测试数据描述如下:
第一行一个正整数n(1≦n≦2×105),表示数字的个数。
第二行n个正整数a(1≦ai≦109),表示每个数字的值。
(保证所有测试数据中，n的总和不超过2×105)
输出描述
对于每组测试数据:
在单独的一行输出一个正整数表示黑色数字的最大总和
样例1
输入
2
5
1 3 3 4 2
4
1 1 1 1
输出
7
2
说明
对于第一组测试数据，我们一开始可以选择j=2,将a2染黑，最终黑色数字为:a2和a4,总和为7最大。
