11570번 - 환상의 듀엣

상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높이가 순서대로 N개 적혀져 있었다. 둘은 악보에 적혀 있는 모든 음들을 노래해야 하며, 각 음은 둘 중 한 사람에 의해서만 불러져야 한다. 예를 들어 악보에 {3, 6, 2, 5, 4}가 적혀져 있을 때, 상덕이가 {3, 2, 4}을 노래하면 희원이는 {6, 5}를 노래할 것이고, 상덕이가 {6, 2, 5}을 노래하면 희원이는 {3, 4}를 노래할 것이다.

노래를 부르다 음의 높이를 변경하는 것은 힘든 일이다. 예를 들어 {4, 6}을 부르는 것은 {4, 4}를 부르는 것에 비해서 음의 변경이 발생하기 때문에 더 힘들다고 볼 수 있다. 희원이는 {a₁, a₂, ..., a_k}라는 음들의 집합을 노래할 때 힘든 정도를 |a₁ - a₂| + |a₂ - a₃| + ... + |a_k-1 - a_k|로 정의했다. 노래를 부르는 사람은 상덕이와 희원이 둘 뿐이므로, 음들을 집합은 두 개가 있을 것이다. 따라서 두 사람이 해당 악보를 노래를 할 때 힘든 정도는 두 집합의 힘든 정도의 합으로 표현될 수 있다.

상덕이와 희원이는 해당 악보를 노래할 때 힘든 정도를 최소화하고 싶다. 예를 들어 악보가 {1, 3, 8, 12, 13}으로 주어진다하자. 앞의 2개를 상덕이가 부르고 뒤의 3개를 희원이가 부르게되면 상덕이의 힘든 정도는 |1 - 3| = 2, 희원이의 힘든 정도는 |8 - 12| + |12 - 13| = 5가 되며 합인 7이 총 힘든 정도가 되고, 이 값은 나올 수 있는 힘든 정도 중에 가장 최솟값이다. 상덕이와 희원이를 위해서 해당 악보를 노래할 때 힘들 수 있는 정도의 최솟값을 알려주는 프로그램을 작성해보자.

첫 번째 줄에는 음의 개수 N (1 ≤ N ≤ 2,000)이 주어진다.

두 번째 줄에는 N개의 음의 높이가 공백(빈 칸)으로 구분되어 주어진다. 각 음의 높이의 범위는 1 이상 1,000,000 이하의 자연수이다.

상덕이과 희원이가 해당 악보를 노래할 때 힘들 수 있는 정도의 최솟값을 출력한다.