D. Cappuccina's Coffee Pairing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ballerina Cappuccina has opened a coffee tasting stand and prepared $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ cups of coffee, where $$$n$$$ is odd.

Each cup has an integer strength. More formally, let $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ be the strengths of the cups.

Before the tasting begins, Cappuccina must discard exactly one cup. She then pairs up all of the remaining cups.

The cost of pairing two cups with strengths $$$x$$$ and $$$y$$$ is $$$|x-y|$$$. The total cost is the sum of the costs of all pairs.

Cappuccina wants the flavors in each pair to be as similar as possible. Help her determine the minimum total cost she can achieve by choosing which cup to discard and how to pair the remaining cups optimally.

Input

The first line contains a single odd integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$, the number of cups of coffee.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$, where $$$a_i$$$ represents the strength of the $$$i$$$-th cup.

Output

Output a single integer, the minimum possible total pairing cost after Cappuccina discards exactly one cup and pairs all remaining cups optimally.

Example
Input
5
3 10 1 11 4
Output
2
Note

In the first test case, the answer is 2 as Cappuccina can remove $$$1$$$ (the third element) and pair up $$$(3, 4)$$$ and $$$(10, 11)$$$. $$$|10 - 11| + |3 - 4| = 2$$$, and it can be shown that this is the minimum score she can achieve.