Add \(2M-N\) zeros to \(A\) to make it a sequence of length \(2M\), and rearrange it to minimize the following value:

\[\sum_{i=1}^{M}(A_{i}+A_{2M+1-i})^{2}.\]

This can be minimized by sorting \(A\), so the problem can be solved in \(O(N\log{N})\) time.

Below, we prove that sorting \(A\) is one of the optimal solutions.

For any \(A\), there is a way to rearrange it without changing the answer to satisfy the following conditions:

• \(A_{i}\leq A_{2M+1-i}\;(1\leq i\leq M)\)
• \(A_{i}\leq A_{i+1}\;(1\leq i\lt M)\)

Therefore, one of the optimal solutions satisfies the above two conditions.

Now, suppose there is an \(i\;(1\leq i\lt M)\) such that \(A_{2M+1-i}\lt A_{2M-i}\) under the two conditions. Then,

\(((A_{i}+A_{2M+1-i})^{2}+(A_{i+1}+A_{2M-i})^{2})-((A_{i}+A_{2M-i})^{2}+(A_{i+1}+A_{2M+1-i})^{2})\)

\(=2(A_{i}A_{2M+1-i}+A_{i+1}A_{2M-i}-A_{i}A_{2M-i}-A_{i+1}A_{2M+1-i})\)

\(=2(A_{i}-A_{i+1})(A_{2M+1-i}-A_{2M-i}).\)

Here, since \(A_{i}-A_{i+1}\leq 0\) and \(A_{2M+1-i}-A_{2M-i}\lt 0\), it holds that \(2(A_{i}-A_{i+1})(A_{2M+1-i}-A_{2M-i})\leq 0\).

Therefore, if there is an \(i\;(1\leq i\lt M)\) that satisfies \(A_{2M+1-i}\lt A_{2M-i}\), swapping \(A_{2M+1-i}\) and \(A_{2M-i}\) maintains or improves the unbalancedness, so there is an optimal solution where no \(i\;(1\leq i\lt M)\) satisfies \(A_{2M+1-i}\lt A_{2M-i}\).

Therefore, there is an optimal solution that satisfies all of the following conditions:

• \(A_{i}\leq A_{2M+1-i}\;(1\leq i\leq M)\)
• \(A_{i}\leq A_{i+1}\;(1\leq i\lt M)\)
• \(A_{2M-i}\leq A_{2M+1-i}\;(1\leq i\lt M)\)

To satisfy these conditions, you just need to rearrange \(A\), which is equivalent to sorting it in ascending order.