워프 포인트

당신은 성간 교통망을 건설하고 있다. 관할 구역에 $N$개의 별이 있고, 목표는 어떤 별에서든 다른 어떤 별로도 갈 수 있게 만드는 것이다. 지금은 모든 별이 서로 단절되어 있어서, 어느 별에서도 아무 데도 갈 수 없다.

성간 교통망 설계자로서 당신은 워프 포인트를 설치할 수 있다. 별에는 $1$부터 $N$까지 번호가 붙어 있고, 워프 포인트를 하나 설치하면 번호가 연속인 별들 사이를 오갈 수 있게 된다. 워프 포인트의 건설 비용은 별과 워프 포인트의 "퍼텐셜"에 따라 달라진다. $i$번째 별의 퍼텐셜은 정수로 주어지며, 워프 포인트의 퍼텐셜은 임의의 정수로 정할 수 있다. 비용은 워프 포인트의 퍼텐셜과 워프 포인트에 포함되는 각 별의 퍼텐셜의 차의 절댓값을 모두 더한 값이다.

워프 포인트는 원하는 만큼 설치할 수 있다. 어떤 별 쌍 사이든 워프 포인트를 이용해 오갈 수 있게 만드는 최소 총비용을 계산하시오.

예제 입력 1에서는 퍼텐셜이 2인 워프 포인트를 하나 설치하는 것이 최선이다.

예제 입력 2에서는 총비용을 최소화하려면 워프 포인트 세 개가 필요하다. 첫 번째 워프 포인트는 첫 번째 별부터 네 번째 별까지를 연결한다. 두 번째 워프 포인트는 네 번째 별부터 여섯 번째 별까지를 연결한다. 세 번째 워프 포인트는 여섯 번째 별부터 열 번째 별까지를 연결한다.

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

$N$

$a_1$ $\dots$ $a_N$

$N$은 별의 개수이다($1 \le N \le 3,000$). $a_1$부터 $a_N$까지는 각 별의 퍼텐셜이다. 이 퍼텐셜은 $-1,000,000,000$ 이상 $1,000,000,000$ 이하의 정수임이 보장된다.

모든 별을 연결하는 최소 총비용을 출력한다.