Little Misha loves to play with counting sticks. He takes counting sticks from his sister, a first grader. Since he rarely gives them back, Mom often has to buy new sticks. Therefore, not all Misha's sticks are the same, but all sticks have an integer length.
Today Misha is building the next figure out of sticks. He started from the corner of the room. We will denote, conditionally, this angle by the coordinate (0, 0). Then Misha lays out the stick parallel to one of the two walls coming from the given corner. We will assume that the walls are even and form an angle of 90 degrees with each other at the point (0, 0). At the same time, Misha never lays out two sticks in a row at the same time parallel to the same wall (in other words, he always alternates the direction of the sticks).
Misha, although he is small and does not know geometry, is always happy if the end of his figure is as far as possible from the starting angle. Help Misha lay out a figure that will make him happy. Any two sticks that Misha places always have at least one point of contact or intersection.
Input
The program receives several lines as input. The first line contains the integer
n (1<=
n <=
100000) — the number of sticks Misha has. The second line contains
n integers
a1,
...,
a n (1 <=
ai <= 10000) - lengths of Misha sticks.
Imprint
Print a single integer —
square of the maximum distance from the corner with coordinate (0,0) to the end point of the shape that Misha built.
Examples
| # |
Input |
Output |
| 1 |
3
1 2 3
| 26 |
| 2 |
4
1 1 2 2
| 20 |