#P9562. [SDCPC 2023] Matching

[SDCPC 2023] Matching

题目描述

Given an integer sequence a1,a2,,ana_1, a_2, \cdots, a_n of length nn, we construct an undirected graph GG from the sequence. More precisely, for all 1i<jn1 \le i < j \le n, if ij=aiaji - j = a_i - a_j, there will be an undirected edge in GG connecting vertices ii and jj. The weight of the edge is (ai+aj)(a_i + a_j).

Find a matching of GG so that the sum of weight of all edges in the matching is maximized, and output this maximized sum.

Recall that a matching of an undirected graph means that we choose some edges from the graph such that any two edges have no common vertices. Specifically, not choosing any edge is also a matching.

输入格式

There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:

The first line contains an integer nn (2n1052 \le n \le 10^5) indicating the length of the sequence.

The second line contains nn integers a1,a2,,ana_1, a_2, \cdots, a_n (109ai109-10^9 \le a_i \le 10^9) indicating the sequence.

It's guaranteed that the sum of nn of all test cases will not exceed 5×1055 \times 10^5.

输出格式

For each test case output one line containing one integer indicating the maximum sum of weight of all edges in a matching.

3
9
3 -5 5 6 7 -1 9 1 2
3
-5 -4 -3
3
1 10 100

30
0
0

提示

For the first sample test case, the optimal choice is to choose the three edges connecting vertex 33 and 55, vertex 44 and 77, and finally vertex 88 and 99. The sum of weight is (5+7)+(6+9)+(1+2)=30(5 + 7) + (6 + 9) + (1 + 2) = 30.

For the second sample test case, as all edges have negative weights, the optimal matching should not choose any edge. The answer is 00.

For the third sample test case, as there is no edge in the graph, the answer is 00.