시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB81436429851.557%

문제

조별 과제를 위해서 수강생 $N$명의 사람의 조를 편성하려고 한다. 모든 사람은 정확히 한 개의 조에 속해야 한다. 원래 한 조는 $2$명으로 이루어져야 하지만, $N$이 홀수이기 때문에 단 하나의 조는 $3$명으로 이루어진다. 다른 $\frac{N-3}{2}$개의 조는 $2$명으로 이루어진다.

성공적인 조별 과제를 위해서는 화기애애한 분위기가 중요하다. 각 학생에게는 고유한 학번이 있으며, 어떤 조의 어색함은 해당 조에 속한 사람의 학번 중 최댓값과 최솟값의 차이로 계산된다.

조를 적절히 편성해서, 편성된 모든 조의 어색함의 합을 최소화하자.

입력

첫 번째 줄에 수강생의 수 $N$이 주어진다. $(3 \le N \lt 500\,000;$ $N$은 홀수$)$

두 번째 줄에 각 학생의 학번을 의미하는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$ 주어지는 $A_i$는 서로 다르다.

출력

조를 적절히 편성해서, 편성된 모든 조의 어색함의 합의 최솟값을 출력하여라.

예제 입력 1

5
3 1 4 5 9

예제 출력 1

7

학번이 $3, 1$인 사람을 한 조로 묶고, $4, 5, 9$인 사람을 한 조로 묶으면 각 조의 어색함은 $(3-1) = 2$와 $(9-4) = 5$이고, 합은 $7$이다.

이 방법이 각 조의 어색함의 합을 최소로 하는 방법이다.

예제 입력 2

7
20 10 9 11 3 18 1

예제 출력 2

6