Lunar New Year and Number Division

题意翻译

【题目描述】 新年来了,Bob 正被他的家庭作业所为难,他需要完成一个划分数字的作业。 Bob 的作业上有 $n$ 个正整数 $a_1,a_2,{\dots},a_n$,其中 $n$ 为偶数,他要把这些数字进行分组,每组至少两个数字,假设分成了 $m$ 组,第 $j$ 组的数字之和是 $s_j$,Bob 需要最小化 $s_j$ 的平方和,即 $\sum^{m}_{j=1} s_j^2$。 Bob 被这题难住了,你可以帮帮他吗? 【输入格式】 第一行一个正偶数 $n$,表示 Bob 的作业上有 $n$ 个数。 接下来一行 $n$ 个整数,表示 Bob 作业上的数。 【输出格式】 输出一行表示 $s_j$ 的最小平方和,即$\sum^{m}_{j=1} s_j^2$,其中 $m$ 为数字组数。 【数据范围】 对于 $100\%$ 的数据,有 $2\leq n\leq 3\times 10^5, 1 \leq a_i \leq 10^4$。

题目描述

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.

输入输出样例

输入样例 #1

4
8 5 2 3

输出样例 #1

164

输入样例 #2

6
1 1 1 2 2 2

输出样例 #2

27

说明

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 $ .