Grow The Tree

题意翻译

有n个木棍，从（0，0）点开始，每次你可以选一根木棍平行于x轴或y轴的摆，但不能有连续两个或以上的木棍是选择同一状态的（只能横竖横竖或竖横竖横地摆）。每次木棍摆的起始位置是上一根木棍的结束位置，问最后一条木棍的终点距离（0，0）点最远的距离的平方最大是多少。

题目描述

Gardener 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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

3
1 2 3

输出样例 #1

26

输入样例 #2

4
1 1 2 2

输出样例 #2

20

说明

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 $ .  

题意翻译

有n个木棍，从（0，0）点开始，每次你可以选一根木棍平行于x轴或y轴的摆，但不能有连续两个或以上的木棍是选择同一状态的（只能横竖横竖或竖横竖横地摆）。每次木棍摆的起始位置是上一根木棍的结束位置，问最后一条木棍的终点距离（0，0）点最远的距离的平方最大是多少。