Maximum Weighted Matching on Constructed Graph

You are given an integer sequence \(a_1, a_2, \cdots, a_n\) of length \(n\). We construct an undirected graph \(G\) from the sequence in the following way: for every pair of indices \(1 \le i .

A matching in an undirected graph is a set of edges no two of which share a common vertex (an empty set of edges is allowed). The task is to find a matching in \(G\) so that the sum of weights of the chosen edges is maximized, and output this maximum sum.

Observations:

• The condition \(i - a_i = j - a_j\) allows us to group vertices by the value \(d = i - a_i\). There is an edge between any two vertices within the same group.
• Since every edge \(\{i,j\}\) in a group contributes \(a_i + a_j\), picking a set of disjoint edges is equivalent to selecting an even-sized subset of vertices from the group and summing their \(a\) values. Vertices that are left unmatched contribute nothing.
• Thus, for each group, our goal is to choose an even subset of vertices (possibly by adding a vertex of value 0 that does not change the sum) so that the total sum is maximized. Notice that if all chosen vertices have positive values, then we want to take as many as possible; if the count of positive numbers is odd and there is no zero to balance the parity, we must remove the smallest positive number from that group.

The final answer is the sum of the optimal contributions from each group.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)).

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) separated by spaces.

outputFormat

Output a single integer, the maximum sum of weights of the matching in the graph \(G\).

sample

3
3 1 2

3