Mathematical platforms

In older games, which have 2D graphics, one can run into the next situation. The hero jumps along the platforms or islands that hang in the air. He must move himself from one side of the screen to the other. The hero can jump from any platform number $i$ to any platform number $k$, spending $(i-k)\ast (i-k)\ast (y_i-y_k)\ast (y_i-y_k)$ energy, where $y_i$ and $y_k$ are the heights where these platforms hang. Obviously energy should be spent frugally.

You are given the heights of the platforms in order from the left side to the right. Can you find the minimum amount of energy to get from the $1$-st (start) platform to the $n$-th (last)?

Input

The first line contains the number of platforms $n(1\le n\le 4000)$. The second line gives $n$ integers — the heights of the platforms, which absolute values are not greater than $200000$.

Output

Print the singe integer which is the minimum amount of energy to get from the $1$-st platform to the $n$-th.

Examples