이상한 토너먼트

천하제일 코딩 대회가 1대1 토너먼트로 열린다. 대회를 운영하는 민호는 참가자마다 코딩력을 정확히 알고 있다. 코딩력이 다른 두 사람이 대결하면 항상 코딩력이 높은 쪽이 이긴다. 그래서 우승자는 사실상 정해져 있다.

민호는 대진표를 따로 짜기 귀찮아서, 참가 신청 순서대로 참가자를 일렬로 세운 뒤 선을 그어 대진표를 만든다. 선은 서로 교차하면 안 된다. 즉 경기는 항상 이웃한 두 그룹 사이에서만 열리고, 각 그룹은 일렬로 선 참가자 중 연속한 구간이다. 한 그룹의 대표는 그 구간에서 코딩력이 가장 높은 참가자다. 선을 어떻게 긋느냐에 따라 참가자마다 치르는 경기 수는 다를 수 있다.

관중이 느끼는 지루함은 경기에 나선 두 사람의 코딩력 차이에 비례한다. 코딩력이 $a$, $b$인 두 사람이 붙은 경기 하나의 지루함을 $|a - b|$로 정의한다.

모든 경기가 끝난 뒤 지루함의 합이 가장 작아지도록 대진표를 그리려 한다. 그 최솟값을 구하여라.

아래 그림은 참가자가 5명이고 코딩력이 신청 순서대로 2017, 100, 20, 30, 70일 때 대진표를 그리는 두 가지 방법이다.

그림 1 최적의 경우 (총 지루함 1997)	그림 2 최악의 경우 (총 지루함 7848)

첫째 줄에 참가자 수 $N$ ($2 \le N \le 500$)이 주어진다. 이어지는 $N$개 줄에 참가 신청 순서대로 각 참가자의 코딩력 $X_i$ ($1 \le X_i \le 100000$)이 한 줄에 하나씩 주어진다. 코딩력이 같은 참가자는 없다.

지루함의 합이 최소가 되도록 대진표를 그렸을 때, 그 합을 첫째 줄에 출력한다.