Dumb Problem
给定长度为 n 的整数序列 a1,…,an。你需要恰好进行一次如下过程:
- 选择 1,2,…,n 的一个排列 p1,…,pn。
- 按照 i=1,2,…,n 的顺序,依次执行api←api+api−1+api+1.
约定 a0=an+1=0。每次赋值使用的是当时序列中的当前值,因此之前已经修改过的值会影响后续操作。
求过程结束后所有元素之和的最大值。
输入格式
第一行一个整数 t(1≤t≤104),表示测试用例数。
每个测试用例第一行一个整数 n(1≤n≤2⋅105)。
第二行 n 个整数 a1,…,an(−108≤ai≤108)。
一个输入文件中所有测试用例的 ∑n≤2⋅105。
输出格式
每个测试用例输出一行一个整数,表示最大可能的元素总和。
样例 1
输入
4
3
1 2 3
4
-1 3 7 6
5
4 1 0 5 2
6
4 -3 7 5 -9 3
输出
22
85
72
79