Problem Description

You are a little jumping frog, and you are especially good at jumping around in all kinds of places.

One day, when you went out to play with your friend Little F, you came across a pile of stones with different heights. The height of the $i$-th stone is $h_i$, and the ground height is $h_0 = 0$. You estimate that the stamina cost to jump from stone $i$ to stone $j$ is $(h_i - h_j) ^ 2$, and the stamina cost to jump from the ground to stone $i$ is $(h_i) ^ 2$.

To show Little F your amazing jumping skills, you decide to jump onto each stone exactly once, and finally stop on any stone. Also, the little frog wants to spend as much stamina as possible.

Of course, you are just a little frog. You can only jump, and you do not know how to jump in a way that shows your skills best.

But you are saved! Little F hands you a computer with “AK” written on it, and you can use a computer program to solve this problem. The almighty computer will tell you how to jump.

So please, you little frog who can write code, write this program and take a solid step toward getting NOIp AK!

Input Format

The first line contains a positive integer $n$, the number of stones.

The second line contains $n$ positive integers, where the $i$-th integer is the height $h_i$ of the $i$-th stone.

Output Format

Output one positive integer in a single line, the maximum stamina cost you can spend.

2
2 1

5

3
6 3 5

49

Hint

Sample Explanation

For both samples, jumping in the order given in the input is one of the optimal solutions.

Constraints

For $1 \leq i \leq n$, $0 < h_i \leq 10 ^ 4$, and all $h_i$ are distinct.

For $10\%$ of the testdata, $n \leq 3$.

For $20\%$ of the testdata, $n \leq 10$.

For $50\%$ of the testdata, $n \leq 20$.

For $80\%$ of the testdata, $n \leq 50$.

For $100\%$ of the testdata, $n \leq 300$.

Translated by ChatGPT 5