Задача №114643. Выращивание дерева
Садоводу Лёше, преподающему школьникам олимпиадную информатику, на день учителя подарили набор деревянных палочек, каждая из которых представляет собой отрезок целочисленной длины. Теперь Леша хочет вырастить из них дерево.
Дерево представляет собой ломаную на плоскости, состоящую из подаренных ему палочек. Ломаная начинается в точке \((0, 0)\). Строя ломаную, Лёша может соединять палочки в любом порядке, располагая каждую горизонтально или вертикально (то есть параллельно осям \(OX\) и \(OY\)). При этом он не может располагать две идущие подряд палочки одновременно горизонтально или вертикально. Лёша хочет сделать так, чтобы конец ломаной был как можно дальше от точки \((0, 0)\). Помогите ему вырастить дерево таким образом!
Первая строка содержит целое число \(n\) (\(1 \leq n \leq 100\,000\)) — количество палочек, подаренных Лёше.
Вторая строка содержит \(n\) целых чисел \(a_1, \ldots, a_n\) (\(1 \leq a_i \leq 10\,000\)) — длины палочек, подаренных Лёше.
В единственной строке выведите одно целое число — \(\textbf{квадрат}\) максимального расстояния от точки \((0, 0)\) до конечной точки дерева.
3 1 2 3
26
4 1 1 2 2
20