팔찌 만들기

용모는 유치원에서 아이들을 위해 자원봉사를 하고 있다.

오늘 활동은 구슬 $N$개를 줄로 이어 팔찌를 만드는 것이다. 각 구슬에는 서로 다른 수가 하나씩 적혀 있고, 두 구슬을 잇는 줄의 길이는 두 구슬에 적힌 수의 차의 절댓값이다. 선생님은 이 활동으로 아이들이 뺄셈을 즐겁게 배우기를 기대한다.

용모는 아이들에게 완성된 팔찌의 견본을 보여주는 역할을 맡았다. 선생님은 용모에게 $N$개의 구슬을 건네며, $N$개의 구슬로 팔찌를 만들되 줄을 가능한 적게 쓰라고 부탁했다. 하지만 자원봉사를 열심히 하느라 지친 용모는 필요한 줄의 최소 길이를 구할 방법이 떠오르지 않았다. 여러분이 용모 대신 $N$개의 구슬로 팔찌를 만드는 데 필요한 줄의 최소 길이를 구해 주자.

첫 번째 줄에 구슬의 개수 $N$이 주어진다.

두 번째 줄에 각 구슬에 적힌 수 $N$개가 공백으로 구분되어 차례로 주어진다.

$N$개의 구슬을 모두 사용하여 조건에 맞게 팔찌를 만들 때 사용하는 줄 길이의 최솟값을 출력한다.

• $3 \le N \le 1{,}000$
• $1 \le$ 구슬에 적힌 수 $\le 10^9$
• 각 구슬에 적힌 수는 모두 다르다.