Peter 有 $n$ 枚炸弹位于一条直线上，第 $i$ 枚炸弹的位置为 $x_i$。每枚炸弹都有一个爆炸半径 $r_i$（$r_i$ 为整数）。当一枚炸弹爆炸时，所有距离不超过其爆炸半径的炸弹也会随之爆炸。爆炸半径为 $r$ 的炸弹成本为 $r^2$。Peter 希望为每枚炸弹选择一个爆炸半径 $r_i$，使得无论最初引爆哪一枚炸弹，最终所有的炸弹都会爆炸。

请帮助 Peter 最小化这 $n$ 枚炸弹的总成本。

输入格式

输入包含多组测试数据。对于每组测试数据： 第一行包含一个整数 $n$ ($1 \le n \le 3000$)，表示炸弹的数量。 第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^6, x_1 < x_2 < \dots < x_n$)。 所有测试数据中 $n$ 的总和不超过 $3000$。

输出格式

对于每组测试数据，输出一行，表示最小总成本。

样例

样例输入 1

5
1 4 5 6 10
3
1 2 6

样例输出 1

51
33