Eradication Sort

No-Weather-too-Extreme Recreational Climbing 동아리 회원들은 7년 전 오늘 첫 등반에 성공했다.

당시 회원들은 사진을 찍기 위해 한 줄로 나란히 섰다. 하지만 등반가들은 키 순서대로 서 있지 않았고, 사진의 순서는 바꿀 수 없다.

사진에서 일부 등반가를 잘라내야 한다.

그림 E.1: 원래 11명이던 사진을 편집해 7명만 남긴 사진이다.

최적해는 사진에 보이는 빈틈의 크기와 개수를 최소화한다. 비용은 편집한 사진에 남는 빈틈 길이의 제곱을 모두 더한 값이다. 예를 들어 개별 등반가 두 명을 제거하고 인접한 두 명을 한 쌍으로 제거하면 총 비용은 $1^2 + 1^2 + 2^2 = 6$이다.

등반가를 제거해서 얻을 수 있는 최소 비용을 구하라.

첫 줄에 사진 속 사람 수 $n$ ($1 \le n \le 10^6$)이 주어진다.

둘째 줄에는 사진 속 사람들의 키를 나타내는 $n$개의 정수 $h_1, h_2, \ldots, h_n$ ($0 \le h \le 10^6$)이 주어진다.

남은 등반가들이 비내림차순을 이루도록 제거했을 때 얻을 수 있는 최소 비용을 출력한다.