Funny Cost

To find the best matching, we can use the following greedy algorithm:

Pick the largest edge, note that this edge should be present in the maximum number of pairs. It means that if the index of this edge is $$$i$$$, you should pick the maximum number of pairs $$$(l, r)$$$ with $$$l \in [1 \ldots i)$$$, $$$r \in [i \ldots n)$$$. Then, you need to add $$$a_i \cdot \min{((i - l), (n - i))}$$$ to the answer and proceed recursively to the problem "find the maximum weight of $$$k$$$ pairs inside the segment" for the larger segment.

From this algorithm it is trivial that for the fixed length $$$n$$$, for the $$$i$$$-th element in the sorted order there is a coefficient $$$b_i$$$, and the answer for any array $$$a_1 \geq a_2 \geq \ldots \geq a_n$$$ is equal to $$$\sum{a_i \cdot b_i}$$$.

You can investigate the algorithm below to prove that $$$b_i$$$ is equal to $$$(\frac{n}{2}!)^2 \cdot$$$ $$${n - i - 2} \choose {\frac{n}{2} - 1}$$$.