题目描述

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

输入格式

第一行：一个整数 n（1 ≤ n ≤ 100000），表示木棍数量。 第二行：n 个整数 a₁...aₙ（1 ≤ aᵢ ≤ 10000），表示每个木棍的长度。

输出格式

打印一个整数，表示从 (0, 0) 到最后一根木棍终点最大可能距离的平方。

输入样例 #1

3  
1 2 3

输出样例 #1

26

输入样例 #2

4  
1 1 2 2

输出样例 #2

20

题目说明

以下两张图分别表示测试样例1和2对应的摆放情况

样例1最终结果是55+11=26，样例2最终结果是44+22=20