#P17961. Dumb Problem

Dumb Problem

Dumb Problem

给定长度为 nn 的整数序列 a1,…,ana_1,\ldots,a_n。你需要恰好进行一次如下过程:

  1. 选择 1,2,…,n1,2,\ldots,n 的一个排列 p1,…,pnp_1,\ldots,p_n。
  2. 按照 i=1,2,…,ni=1,2,\ldots,n 的顺序,依次执行api←api+api−1+api+1.a_{p_i}\leftarrow a_{p_i}+a_{p_i-1}+a_{p_i+1}.

约定 a0=an+1=0a_0=a_{n+1}=0。每次赋值使用的是当时序列中的当前值,因此之前已经修改过的值会影响后续操作。

求过程结束后所有元素之和的最大值。

输入格式

第一行一个整数 tt(1≤t≤1041\le t\le10^4),表示测试用例数。

每个测试用例第一行一个整数 nn(1≤n≤2⋅1051\le n\le2\cdot10^5)。 第二行 nn 个整数 a1,…,ana_1,\ldots,a_n(−108≤ai≤108-10^8\le a_i\le10^8)。

一个输入文件中所有测试用例的 ∑n≤2⋅105\sum n\le2\cdot10^5。

输出格式

每个测试用例输出一行一个整数,表示最大可能的元素总和。

样例 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