408652: GYM103256 B Huron Jam

Huron Jam is a competition for university students organized by the popular competitive programming site HuronForces. The participants form teams of two students from the same university and take part in multiple rounds.

Edgardo is responsible for registering the teams for ESCOM. There are $$$n$$$ ($$$n$$$ is an even number) students in ESCOM available to compete in Huron Jam and Edgardo will divide them in $$$\frac{n}{2}$$$ teams of two people to participate in the competition.

Each student has a skill level $$$a_i$$$. If the students with skill levels $$$x$$$ and $$$y$$$ form a team, then the imbalance of that team would be considered to be $$$|x-y|$$$. Edgardo knows that maintaining the imbalance of the teams as low as possible is important for the success of the university in the competition, so he wants to select the teams while minimizing the total imbalance of them. The total imbalance is defined as the sum of the imbalance of the $$$\frac{n}{2}$$$ teams.

Help Edgardo to find the minimum total imbalance that he can achieve when dividing the students in $$$\frac{n}{2}$$$ teams. Note that each student must be in exactly one team.

Recall that $$$|x|$$$ is defined to be the absolute value of $$$x$$$. In other words, if $$$x$$$ is an integer number, then $$$|x|=x$$$ if $$$x \geq 0$$$ and $$$|x|=-x$$$ when $$$x < 0$$$.

The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 1000$$$ and $$$n$$$ is even) $$$-$$$ the number of available students in ESCOM.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ in increasing order ($$$1 \leq a_1 \leq a_2 \leq \dots \leq a_n \leq 1000$$$) $$$-$$$ the skill level of the students in ESCOM.

In the first line print a single integer $$$-$$$ the minimum possible total imbalance.

2
1 1000

999

6
1 3 4 6 7 32

29

8
1 1 2 3 3 6 8 10

6

4
1 2 3 4

2

34
512 514 557 565 570 574 588 601 620 623 625 626 645 659 674 680 734 740 775 778 786 793 836 856 863 911 925 926 929 933 941 947 958 984

172

In the first example, there are $$$2$$$ students, so Edgardo can form only one team: a team formed with students with skill level $$$1$$$ and $$$1000$$$. The total imbalance is $$$|1-1000|=999$$$.

In the second example, there are $$$6$$$ students and Edgardo need to form $$$\frac{6}{2}=3$$$ teams. He can select students with skill level $$$6$$$ and $$$4$$$ for the first team, students with skill level $$$7$$$ and $$$32$$$ for the second team and students with skill level $$$3$$$ and $$$1$$$ for the third team. The total imbalance is equal to $$$|6-4|+|7-32|+|3-1|=29$$$. In any other division of the students in $$$3$$$ teams the total imbalance will be greater or equal to $$$29$$$.