수직선 위에 놓인 개 표식의 좌표를 오름차순으로 나열한 수열 가 주어진다. 모든 좌표는 서로 다른 정수이다.
수열 의 양 끝 원소만 남을 때까지 다음 연산을 반복한다.
양 끝이 아닌 원소 를 제거하고 다음 비용을 지불한다.
지불한 비용의 합의 최솟값을 구해 보자.
첫 번째 줄에 표식의 개수 이 주어진다.
두 번째 줄에 표식의 좌표 이 공백으로 구분되어 주어진다.
지불한 비용의 합의 최솟값을 출력한다.
좌표가 , , 인 표식을 차례대로 제거하면 각 연산의 비용은 , , 이고 총비용은 이다.