32564번 - Eradication Sort 다국어

문제

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, we took a picture of all the members standing together in one row. However, the photograph looks messy, as the climbers were not standing in order of height, and we have no way to reorder them.

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

Figure E.1: This picture of 7 (formerly 11) climbers was edited to solve Sample Input 3.

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

Find the minimum possible cost you can reach by removing climbers.

입력

• The number of people in the photo $n$ (1ドル \le n \le 10^6$).
• $n$ integers representing the heights of people in the photo, $h_1 \ldots h_n$ (0ドル \le h \le 10^6$).

출력

Output the minimum cost achieved by removing climbers from the photo, such that the remaining climbers in the photo make a non-decreasing sequence.

제한

힌트