e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

ADA University - February 3 - Dijkstra

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) * (i - k) * (yi - yk) * (yi - yk) energy, where yi and yk 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 (1n4000). 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.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
4
1 2 3 30
Output example #1
731
Author Илья Порублёв
Source Летняя школа Севастополь 2013, Волна 1, День 2