题目描述

你有一只小跳蛙， 为了让小跳蛙有充足的运动量， 你找了一堆高矮不同的石头， 其中第 $i$ 块的 石头高度为 $h_i$ ， 地面的高度是 $h_0$ = 0。从第 $i$ 块石头跳到第 $j$ 块石头上耗费小跳蛙的体力($h_i - h_j )^2$， 从地面跳到第 $i$ 块石头耗费的体力值是 $(h_i)^2$。

为了小跳蛙的健康， 你决定让小跳蛙跳到每个石头上各一次， 并最终停在任意一块石头上， 并且 让小跳蛙耗费尽可能多的体力值。

当然， 身为程序员的你可以使用计算机程序帮你解决这个问题。

输入格式

第一行， 一个正整数 $n$， 表示石头个数。

第二行有 $n$ 个正整数， 表示第 $i$ 块石头的高度 $h_i$。

输出格式

输出一行一个正整数， 表示小跳蛙可以耗费的体力值的最大值。

样例

2
2 1

5

3
6 3 5

49

样例解释

两个样例按照输入给定的顺序依次跳上去就可以得到最优方案之一

数据规模与约定

• 对于 $1≤i≤n$， 有 $0< h_i≤10^4$ ， 且保证$h_i$ 互不相同
• 对于 10% 的数据， $n≤3$
• 对于 20% 的数据， $n≤10$
• 对于 50% 的数据， $n≤20$
• 对于 80% 的数据， $n≤50$
• 对于 100% 的数据， $n≤300$