题目描述

平方拼图是用一堆牌来玩的，这些牌排成一行，每一张牌都包含一个正整数。在移动过程中，玩家从一行中取出一张牌，并按所取牌上的数字与左右两张牌上的数字之和的平方来得分。如果取出最左的卡片，就只计算它和右边卡片之和的平方。取最右的卡片，就只计算它和左边卡片之和的平方。

我们的目标是采取某种顺序取牌以尽量增加总得分。

例如，如果一行中的牌包含数字 $20,1,50$，玩家可能会先拿一张 $1$ 的牌，然后拿 $20$ 和 $50$ 的牌，这样的得分为

$(20+1+50)^2+(20+50)^2+50^2=5041+4900+2500=12441$。

如果它按照相反的顺序拿牌，即先拿 $50$，再拿 $20$，最后拿 $1$，这样的得分为

$(1+50)^2+(20+1)^2+1^2=2601+441+1=3043$。

输入格式

第一行为一个整数 $N$（$3\le N\le100$），表示卡牌的数量。

接下来 $N$ 个数字，第 $i$ 个数字 $a_{i}$（$1\le a_{i}\le100$）表示第 $i$ 张牌上的数字。

输出格式

一个数字，表示最大得分。

来源

浩轩OJ 4380 · 原题图片

数据范围与约定

第一行为一个整数 $N$（$3\le N\le100$），表示卡牌的数量。

接下来 $N$ 个数字，第 $i$ 个数字 $a_{i}$（$1\le a_{i}\le100$）表示第 $i$ 张牌上的数字。

可见测试数据

输入数据 1

3
20 1 50

输出数据 1

12441

输入数据 2

5
3 3 7 2 10

输出数据 2

1286

输入数据 3

10
11 5 9 21 1 18 22 23 9 4

输出数据 3

19086