Computer game (platforms) with quadratic jumps

Computer game (platforms) with quadratic jumps

Can you remember at least single your acquaintance, who is less than twenty years old and didn't play computer games in childhood? If yes, you might not know this kind of entertainment. But it wouldn't prevent you to solve this problem.

In older games, which have 2D graphics, one can run into the next situation. The hero jumps along the platforms that hang in the air. He must move himself from one side of the screen to the other. When the hero jumps from one platform to the neighboring, he spends |y2-y1|2 energy, where y1 and y2 are the heights where these platforms hang. Also the hero has super skill  he can make a super jump that allows him to skip one platform, but it takes him3·|y3-y1|2 energy. 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 nd the minimum amount of energy to get from the 1-st (start) platform to the N-th (last)?


The first line contains the number of platforms N (2N100000). The second line gives N integers the heights of the platforms, which absolute values are not greater than 4000.


Print the integer which is the minimum amount of energy to get from the 1-st platform to the N-th (assuming, that player is forbidden to use cheat codes).

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