Eradication Sort

Time limit2sMemory limit1024 MB

Summary

Remove climbers so the rest form a non-decreasing sequence, minimizing the sum of squared lengths of the gaps left behind.

Level: Hard8 of 10
Topics: Dynamic programming, Segment tree, Sorting
Solved: No attempts yet

Problem

The members of the No-Weather-too-Extreme Recreational Climbing society completed their first successful summit seven years ago to this day!

At the time, the members stood together in one row for a photograph. However, the climbers were not standing in order of height, and the photo cannot be reordered.

You will need to cut some of the climbers out of the picture.

Figure E.1: A photo of 7 climbers, edited down from an original group of 11.

An optimal solution minimizes the size and number of visible gaps in the photo. The cost is the sum of the squares of the lengths of the gaps left in the edited photo. For example, if two individual climbers are removed and one pair of adjacent climbers is removed, the total cost is $1^2 + 1^2 + 2^2 = 6$ .

Find the minimum cost you can reach by removing climbers.

Input

The first line contains the number of people in the photo, $n$ ( $1 \le n \le 10^6$ ).

The second line contains $n$ integers $h_1, h_2, \ldots, h_n$ , the heights of the people in the photo ( $0 \le h \le 10^6$ ).

Output

Output the minimum cost achieved by removing climbers so that the remaining climbers form a non-decreasing sequence.

Examples3

Example 1
Input
```
7
1 2 3 0 5 6 7
```
Expected output
```
1
```
Example 2
Input
```
9
4 5 6 4 2 3 6 6 6
```
Expected output
```
8
```
Example 3
Input
```
11
3 6 12 7 7 7 6 8 10 5 5
```
Expected output
```
6
```