园丁阿列克谢向高中生教授竞争性编程。为了祝贺阿列克谢教师节,学生们送给他一系列木棍,每根木棍的长度都是整数。现在阿列克谢想用它们长成一棵树。
这棵树看起来像平面上的一条折线,由所有木棍组成。多段线从点 $$$(0, 0)$$$ 开始。在构建折线时,Alexey 将以任意顺序将木棍一根一根地固定在其上。每根棍子必须是垂直或水平的(即平行于 $$$OX$$$ 或 $$$OY$$$ 轴)。不允许两个连续的木棍同时水平对齐或同时垂直对齐。请参阅下图以了解详情。
Alexey 想要制作一条折线,使其末端尽可能远离 $$$(0, 0)$$$。请帮助他以这种方式种植这棵树。
请注意,定义树形式的折线可能具有自交和自接触,但可以证明最佳答案不包含任何自交或自接触。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100\,000$$$) — Alexey 作为礼物得到的木棍数量。
第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10\,000$$$) — 木棍的长度。
输出
打印一个整数 - 从 $$$(0, 0)$$$ 到树末端的最大可能距离的平方。
示例
输入 #1
3 1 2 3
输出 #1
26
输入 #2
4 1 1 2 2
输出 #2
20
注意
下图显示了示例测试的最佳树。第一个示例中的平方距离等于 $$$5 \cdot 5 + 1 \cdot 1 = 26$$$,第二个示例中的平方距离等于 $$$4 \cdot 4 + 2 \cdot 2 = 20$$$。