Frog Leaps

Frogs want to enter the programming contest in Amsterdam too. Getting there means crossing a lot of rivers. This frog is in good shape and jumps as far as it wants, but a jump of $i$ meters costs $i^2$ units of energy. The only way across a river is to jump from stop to stop.

The frog is lazy and wants to spend as little energy as possible. Compute the minimum amount of energy it needs to reach Amsterdam.

The first line contains one integer $n$, the number of stops ($2 \le n \le 10^6$).

Each of the next $n$ lines contains one integer $x_i$, the position of the $i$-th stop in meters ($0 \le x_i \le 10^6$, $x_i < x_{i+1}$).

The frog starts at the first stop $x_0$, and Amsterdam is at the last stop $x_{n-1}$.

Print one integer, the minimum number of units of energy the frog needs to reach Amsterdam.