Group Project

Interview

Time limit1sMemory limit512 MB

Summary

Split N students with distinct IDs into pairs and one triple so that the sum of each team's max-min ID gap is minimized.

Level: Medium5 of 10
Topics: Sorting, Dynamic programming
Solved: No attempts yet

Problem

A class of $N$ students must be split into teams for a group project. Every student must belong to exactly one team. A team should normally have 2 members, but since $N$ is odd, exactly one team has 3 members. The other $\frac{N-3}{2}$ teams have 2 members each.

A successful group project needs a friendly atmosphere. Each student has a unique student ID. The awkwardness of a team is the difference between the largest and smallest student IDs in that team.

Form the teams so that the sum of awkwardness over all teams is minimized.

Input

The first line contains the number of students $N$ . ( $3 \le N < 500\,000$ , $N$ is odd)

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$ , separated by spaces, where $A_i$ is the student ID of the $i$ -th student. ( $1 \le A_i \le 10^9$ ) All $A_i$ are distinct.

Output

Print the minimum possible sum of awkwardness over all formed teams.

Examples2

Example 1
Input
```
5
3 1 4 5 9
```
Expected output
```
7
```
Example 2
Input
```
7
20 10 9 11 3 18 1
```
Expected output
```
6
```