C. Лунный новый год и разделение чисел
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Приближается лунный новый год, а Боб все еще мучается со своей домашней работой — задачей о разделении чисел.

Даны $$$n$$$ положительных целых чисел $$$a_1, a_2, \ldots, a_n$$$, где $$$n$$$ всегда четно. Боб должен разделить эти числа на группы, причем каждая группа должна содержать хотя бы $$$2$$$ числа. Предположим, что числа разделены на $$$m$$$ групп, и сумма чисел в $$$j$$$-й группе равна $$$s_j$$$. Цель Боба — минимизировать сумму квадратов $$$s_j$$$, то есть $$$$$$\sum_{j = 1}^{m} s_j^2.$$$$$$

Боб никак не может решить эту задачу. Можете ему помочь?

Входные данные

Первая строка содержит четное целое число $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$), обозначающее, что в домашней работе Боба даны $$$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$$$ — число групп чисел.

Примеры
Входные данные
4
8 5 2 3
Выходные данные
164
Входные данные
6
1 1 1 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$$$.