题目描述

小珅是一只身手矫健的小跳蛙，最擅长在高低不同的石头上跳跃。这天，他和伙伴小泽来到溪边，眼前摆着 $n$ 块高度各异的石头。

小珅想在小泽面前秀出最强弹跳力：他要从地面出发，跳到每块石头上恰好一次，最后停在任意一块石头上（不能从石头跳回地面）。从地面跳到第 $i$ 块石头，体力消耗为 $(h_i)^2$；从第 $i$ 块石头跳到第 $j$ 块石头，体力消耗为 $(h_i - h_j)^2$。

小珅希望消耗的体力总和尽可能大，但他算不出最优路线，便求助于你 —— 请你帮他计算最大体力消耗值。

输入格式

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

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

输出格式

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

输入输出样例

2
2 1

5

3
6 3 5

49

说明/提示

样例解释

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

数据范围

对于 $1 \leq i \leq n$，有 $0 < h_i \leq 10 ^ 4$，且保证 $h_i$ 互不相同。

对于 $10\%$ 的数据，$n \leq 3$；

对于 $20\%$ 的数据，$n \leq 10$；

对于 $50\%$ 的数据，$n \leq 20$；

对于 $80\%$ 的数据，$n \leq 50$；

对于 $100\%$ 的数据，$n \leq 300$。

1
1

1