시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 89 38 32 47.059%

문제

영선이와 효빈이는 노래를 부르러 노래방에 갔다.

음의 높이는 1부터 1,000,000 까지로 나누어져 있으며, 1이 낮은 음, 1,000,000이 높은 음이다. 두 사람은 모든 음을 음정이 어긋나지 않게 부를 수 있다.

노래는 음의 연속으로 이루어져 있다. 노래의 음은 두 사람 중에 한 사람만 불러야 한다.

각 사람이 느끼는 노래의 난이도는 연속한 부른 음의 차이의 합으로 구할 수 있다. 예를 들어, 영선이가 8, 8, 13, 12를 불렀다면, 난이도는 |8-8| + |13-8| + |12-13| = 0+5+1 = 6 이다.

영선이와 효빈이는 두 사람이 느끼는 노래의 난이도의 합이 최소가 되게 부르는 음을 나누려고 한다. 이때, 두 사람이 느끼는 노래의 난이도의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노래에 포함된 음의 개수 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 노래에 포함된 음이 순서대로 주어진다.

출력

두 사람이 느끼는 노래의 난이도의 합의 최솟값을 출력한다.

예제 입력 1

5
1 3 8 12 13

예제 출력 1

7

예제 입력 2

5
1 5 6 2 1

예제 출력 2

3

예제 입력 3

8
5 5 5 5 4 4 4 4

예제 출력 3

0

힌트

예제 1의 경우에 영선이가 처음 두 음을 부르고, 효빈이가 뒤의 세 음을 부르면 최소가 된다.

예제 2의 경우에는 영선-효빈-효빈-영선-영선 순서대로 노래를 부르면 최소가 된다.

출처