In a classroom, there are students. The -th student has skill c_i. A teacher is holding an exercise that requires working in pairs. Initially, students 2i-1 and are paired, for each from to .
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 to 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 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 (2 \le n \le 100\:000).
The second line of the input contains 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.
Example 1
Example 2
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.