train_ex

Problem Description

The area north of Squeaky City is very mountainous; jagged mountains protrude from the ground, and deep ravines cut through the earth. Traversing such land is an arduous task; it takes fit mountaineers a month to travel to the North Lands. To enhance trade, the rulers of both cities decide to build a train track to connect both cities.

Planning the alignment of train tracks is a very important task. Trains (especially the old diesel kind) will have to slow down to a crawl when it is climbing, but it can travel at the maximum speed limit when travelling on level tracks or when travelling downwards.

Squeaky City is at sea level, and the North Lands on a plateau at 10⁹ metres above sea level.

The engineering team has identified N equally spaced locations in a straight line between Squeaky City and the North Lands. These locations are the only suitable locations to build the start or end of a bridge (or tunnel). You are to connect this points by a set of train tracks such that the no part of the tracks from the North Lands to Squeaky City is travelling in the upward direction.

However, the cost of bridges (or tunnels) depends on their length. Specifically, the price of each bridge (or tunnel) is proportional to the square of the distance (on ground level) between the two endpoints. You are to minimise the total cost of the bridges (or tunnels).

In other words, you are given a set of points numbered 1 to K; the first point is of height 10⁹, the Kth point is of height 0, and the heights of all other points are arbitrary but between 0 and 10⁹ inclusive. You are to find a set of lines S connecting one point to another, to indirectly connect the first point to the last point, such that the sum of the squares of the horizontal distances of lines in S is minimal.

Input

The first line contains a single integer N, the number of equally spaced locations (excluding the start and end point).

This is followed by N lines. The ith line contains a single integer, the height of the ith point.

Output

A single integer, the minimum total cost, assuming that the price of a bridge between two consecutive locations is 1.

Constraints

Subtask 1 (10 points): 1 ≤ N ≤ 20

Subtask 2 (20 points): 1 ≤ N ≤ 10000

Subtask 3 (70 points): 1 ≤ N ≤ 50000

Subtask 4: Sample

Sample Input

3
100
50
90

Sample Output

6

Explanation for Sample Output

Heights: 	1000000000	100	50 	90	0
Bridges:	   |-------------|--------------|-------|

A bridge is constructed from North Lands to the first point, costing 1*1 = 1

A second bridge is constructed from the first point to the third point, costing 2*2=4

The last bridge is between Squeaky City and the third point, costing 1*1 = 1

Do note that the bridges constructed ensures that the path from North Lands to Squeaky City is not strictly not ascending.