410789: GYM104114 E Exercise

In a classroom, there are $$$2n$$$ students. The $$$i$$$-th student has skill $$$c_i$$$. A teacher is holding an exercise that requires working in pairs. Initially, students $$$2i-1$$$ and $$$2i$$$ are paired, for each $$$i$$$ from $$$1$$$ to $$$n$$$.

Now, the teacher wants to form new pairs $$$(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$$$ with the following conditions:

• Each student is in exactly one pair. That is, each number from $$$1$$$ to $$$2n$$$ appears among numbers $$$a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$$$ exactly once.

• No two students that were in a pair before will be in a pair again. That is, there are no $$$1 \le i, j \le n$$$ such that $$$a_i = 2j-1, b_i = 2j$$$, or $$$a_i = 2j, b_i = 2j-1$$$.

The teacher wants to minimize the sum of differences in skills over the $$$n$$$ pairs, as this would be more productive. In other words, $$$|c_{a_1} - c_{b_1}| + |c_{a_2} - c_{b_2}| + \ldots + |c_{a_n} - c_{b_n}|$$$ should be as small as possible.

What is the smallest value of $$$|c_{a_1} - c_{b_1}| + |c_{a_2} - c_{b_2}| + \ldots + |c_{a_n} - c_{b_n}|$$$ the teacher can achieve?

The first line of the input contains a single integer $$$n$$$ $$$(2 \le n \le 100\:000)$$$.

The second line of the input contains $$$2n$$$ integers $$$c_1, c_2, \ldots, c_{2n}$$$ $$$(0 \le c_i \le 10^9)$$$  — the skills of the students.

Output a single integer  — the smallest possible value of $$$|c_{a_1} - c_{b_1}| + |c_{a_2} - c_{b_2}| + \ldots + |c_{a_n} - c_{b_n}|$$$ that the teacher can achieve.

2
1 2 3 4

4

3
1 9 3 4 2 6

7

In the first example, the teacher can pair up the first student with the third and the second student with the fourth, getting $$$|3 - 1| + |4 - 2| = 4$$$.

In the second example, the teacher can pair up the first student with the third, the second with the sixth, and the fourth with the fifth, getting $$$|1 - 3| + |9 - 6| + |4 - 2| = 7$$$.