Маленький Миша любит играть счетными палочками. Счетные палочки он берет у своей сестры первоклассницы. Так как он редко возвращает их назад, маме приходится часто покупать новые палочки. Поэтому не все палочки у Миши одинаковые, но все палочки имеют целочисленную длину.
Сегодня Миша строит из палочек следующую фигуру. Он начал из угла комнаты. Мы с вами обозначим, условно, этот угол координатой (0, 0). Дальше Миша выкладывает палочку параллельно одной из двух стен, исходящей из данного угла. Будем считать, что стены ровные и образуют друг с другом в точке (0, 0) угол 90 градусов. При этом, Миша никогда не выкладывает две подряд палочки одновременно параллельно одной и той же стене (другими словами, он всегда чередует направление палочек).
Миша, хоть и маленький и не знает геометрии, но все же всегда радуется, если конец его фигуры находится как можно дальше от стартового угла. Помогите Мише выложить фигуру, которая его обрадует. Любые две палочки, которые выкладывает Миша всегда имеют минимум одну точку касания или пересечения.
Входные данные
Программа получает на вход несколько строк. Первая строка содержит целое число
n (1<=
n <=
100000) — количество палочек, которые есть у Миши. Вторая строка содержит
n целых чисел
a1,
...,
an (1 <=
ai <= 10000) - длины Мишиных палочек.
Выходные данные
Выведите одно целое число —
квадрат максимального расстояния от угла с координатой (0,0) до конечной точки фигуры, которую построил Миша.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
1 2 3 |
26 |
| 2 |
4
1 1 2 2 |
20 |