A. Magikarp Jump
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp dreams of becoming a jumping champion and eventually evolving into a Gyarados! For now, he is practicing on a row of $$$n$$$ spots, numbered $$$1$$$ through $$$n$$$. The height of spot $$$i$$$ is $$$h_i$$$.

Magikarp starts at spot $$$1$$$ and wants to reach spot $$$n$$$. From spot $$$i$$$, he can jump to spot $$$i+1$$$, $$$i+2$$$, or $$$i+3$$$, as long as the destination does not exceed $$$n$$$. A jump from spot $$$i$$$ to spot $$$j$$$ costs $$$$$$ (h_i-h_j)^2 $$$$$$ energy. The total energy cost is the sum of the costs of all his jumps.

What is the minimum total energy cost for Magikarp to reach spot $$$n$$$?

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the number of spots.

The second line contains $$$n$$$ integers $$$h_1,h_2,\ldots,h_n$$$ ($$$0 \le h_i \le 10^6$$$) — the heights of the spots.

Output

Output a single integer — the minimum total energy cost for Magikarp to reach spot $$$n$$$.

Examples
Input
6
10 30 20 40 10 20
Output
100
Input
7
0 1000000 1000000 0 1000000 1 1000000
Output
999998000002
Input
4
1 100 100 1
Output
0
Input
1
7
Output
0
Note

In the first sample, Magikarp can jump from spot $$$1$$$ to spot $$$3$$$, then to spot $$$6$$$. The total cost is $$$(10-20)^2+(20-20)^2=100$$$, which is the minimum possible.

In the second sample, one optimal route visits spots $$$1,4,6,7$$$, using jumps of lengths $$$3,2,1$$$. The total cost is $$$$$$ (0-0)^2+(0-1)^2+(1-10^6)^2=999998000002. $$$$$$

In the third sample, Magikarp can jump directly from spot $$$1$$$ to spot $$$4$$$. Both spots have height $$$1$$$, so the cost is $$$0$$$.

In the fourth sample, Magikarp is already at spot $$$n$$$, so he does not need to jump. The total cost is $$$0$$$.