長さ $n$ の整数列 $a_1, a_2, \cdots, a_n$ が与えられます。この列から無向グラフ $G$ を構成します。具体的には、すべての $1 \le i < j \le n$ に対し、$i - j = a_i - a_j$ ならば $G$ に頂点 $i$ と $j$ を結ぶ無向辺が存在します。その辺の重みは $(a_i + a_j)$ です。
マッチングに含まれるすべての辺の重みの総和が最大となる $G$ のマッチングを求め、その最大の総和を出力してください。
無向グラフのマッチングとは、どの $2$ 辺も共通の頂点を持たないように、グラフからいくつかの辺を選ぶことです。特に、辺を $1$ 本も選ばないものもマッチングです。
入力
複数のテストケースがあります。入力の最初の行には、テストケースの個数を表す整数 $T$ が与えられます。各テストケースについて:
最初の行には、列の長さを表す整数 $n$ が与えられます($2 \le n \le 10^5$)。
次の行には、列を表す $n$ 個の整数 $a_1, a_2, \cdots, a_n$ が与えられます($-10^9 \le a_i \le 10^9$)。
すべてのテストケースにわたる $n$ の総和は $5 \times 10^5$ 以下であることが保証されます。
出力
各テストケースについて、マッチングに含まれるすべての辺の重みの総和の最大値を表す整数を $1$ 行に出力してください。
入出力例
入力 1
3 9 3 -5 5 6 7 -1 9 1 2 3 -5 -4 -3 3 1 10 100
出力 1
30 0 0
注記
最初のテストケースの例では、頂点 $3$ と $5$、頂点 $4$ と $7$、頂点 $8$ と $9$ を結ぶ $3$ 本の辺を選ぶのが最適です。重みの総和は $(5 + 7) + (6 + 9) + (1 + 2) = 30$ です。
$2$ 番目のテストケースの例では、すべての辺の重みが負なので、最適なマッチングは辺を $1$ 本も選びません。答えは $0$ です。
$3$ 番目のテストケースの例では、グラフに辺がないため、答えは $0$ です。