Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Grow The Tree

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputGardener Alexey teaches competitive programming to high school students. To congratulate Alexey on the Teacher's Day, the students have gifted him a collection of wooden sticks, where every stick has an integer length. Now Alexey wants to grow a tree from them.

The tree looks like a polyline on the plane, consisting of all sticks. The polyline starts at the point $$$(0, 0)$$$. While constructing the polyline, Alexey will attach sticks to it one by one in arbitrary order. Each stick must be either vertical or horizontal (that is, parallel to $$$OX$$$ or $$$OY$$$ axis). It is not allowed for two consecutive sticks to be aligned simultaneously horizontally or simultaneously vertically. See the images below for clarification.

Alexey wants to make a polyline in such a way that its end is as far as possible from $$$(0, 0)$$$. Please help him to grow the tree this way.

Note that the polyline defining the form of the tree may have self-intersections and self-touches, but it can be proved that the optimal answer does not contain any self-intersections or self-touches.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 100\,000$$$) — the number of sticks Alexey got as a present.

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10\,000$$$) — the lengths of the sticks.

Output

Print one integer — the square of the largest possible distance from $$$(0, 0)$$$ to the tree end.

Examples

Input

3 1 2 3

Output

26

Input

4 1 1 2 2

Output

20

Note

The following pictures show optimal trees for example tests. The squared distance in the first example equals $$$5 \cdot 5 + 1 \cdot 1 = 26$$$, and in the second example $$$4 \cdot 4 + 2 \cdot 2 = 20$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2021 07:25:54 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|