农历新年即将来临,鲍勃正在为他的家庭作业而苦苦挣扎——一道数除法问题。
Bob 的作业纸上有 $$$n$$$ 正整数 $$$a_1, a_2, \ldots, a_n$$$,其中 $$$n$$$ 始终为偶数。 Bob 被要求将这些数字分成几组,每组必须至少包含 $$$2$$$ 数字。假设将数字分为 $$$m$$$ 组,第 $$$j$$$ 组中的数字之和为 $$$s_j$$$。 Bob 的目标是最小化 $$$s_j$$$ 的平方和,即 $$$$$$\sum_{j = 1}^{m} s_j^2.$$$$$$
鲍勃对这个难题感到困惑。你能帮他解决一下吗?
输入
第一行包含一个偶数 $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$),表示 Bob 的作业纸上有 $$$n$$$ 个整数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^4$$$),描述需要处理的数字。
输出
一行包含一个整数,表示$$$s_j$$$的平方和的最小值,即$$$$$$\sum_{i = j}^{m} s_j^2,$$$$$$,其中$$$m$$$是组数。
示例
输入 #1
4 8 5 2 3
输出 #1
164
输入 #2
6 1 1 1 2 2 2
输出 #2
27
注意
在第一个示例中,最佳解决方案之一是将这些 $$$4$$$ 数字分为 $$$2$$$ 组 $$$\{2, 8\}, \{5, 3\}$$$。因此答案是 $$$(2 + 8)^2 + (5 + 3)^2 = 164$$$。
在第二个示例中,最佳解决方案之一是将这些 $$$6$$$ 数字分为 $$$3$$$ 组 $$$\{1, 2\}、\{1, 2\}、\{1, 2\}$$$。因此答案是 $$$(1 + 2)^2 + (1 + 2)^2 + (1 + 2)^2 = 27$$$。