题目描述

园丁 Alexey 教授高中生竞赛编程。为了庆祝教师节，学生们送给了 Alexey 一组木棍，每根木棍的长度都是整数。现在 Alexey 想用这些木棍“种”一棵树。

这棵树在平面上表现为一条折线，由所有木棍组成。折线从点 $(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)$ 到树终点的最大可能距离的平方。

说明/提示

下图展示了样例测试的最优树形。第一个样例的距离平方为 $5 \cdot 5 + 1 \cdot 1 = 26$，第二个样例的距离平方为 $4 \cdot 4 + 2 \cdot 2 = 20$。

由 ChatGPT 4.1 翻译

样例

3
1 2 3

26

4
1 1 2 2

20