CF1106C Lunar New Year and Number Division

Lunar New Year is approaching, and Bob is struggling with his homework – a number division problem. There are $ n $ positive integers $ a_1, a_2, \ldots, a_n $ on Bob's homework paper, where $ n $ is always an even number. Bob is asked to divide those numbers into groups, where each group must contain at least $ 2 $ numbers. Suppose the numbers are divided into $ m $ groups, and the sum of the numbers in the $ j $ -th group is $ s_j $ . Bob's aim is to minimize the sum of the square of $ s_j $ , that is $\sum_{j = 1}^{m} s_j^2. $ Bob is puzzled by this hard problem. Could you please help him solve it?

The first line contains an even integer $ n $ ( $ 2 \leq n \leq 3 \cdot 10^5 $ ), denoting that there are $ n $ integers on Bob's homework paper. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^4 $ ), describing the numbers you need to deal with.

A single line containing one integer, denoting the minimum of the sum of the square of $ s_j $ , which is $ $$$\sum_{i = j}^{m} s_j^2, $ $ where $ m$$$ is the number of groups.

In the first sample, one of the optimal solutions is to divide those $ 4 $ numbers into $ 2 $ groups $ \{2, 8\}, \{5, 3\} $ . Thus the answer is $ (2 + 8)^2 + (5 + 3)^2 = 164 $ . In the second sample, one of the optimal solutions is to divide those $ 6 $ numbers into $ 3 $ groups $ \{1, 2\}, \{1, 2\}, \{1, 2\} $ . Thus the answer is $ (1 + 2)^2 + (1 + 2)^2 + (1 + 2)^2 = 27 $ .