Minimize Sum of Distances to Warehouses

Choose any two warehouse positions on the number line; each center goes to its nearer warehouse, and the sum of all centers' distances should be minimized. The warehouses may coincide, and neither is required to serve any center.

输入格式

The first line contains n, and the second line contains n values dist_centers. The original gives no value ranges; this site sets 1≤n≤200000, −10⁹≤position≤10⁹.

输出格式

Output a single integer answer.

样例 1

输入：

4
1 2 10 11

输出：

2

样例 2

输入：

1
7

输出：

0

样例 3

输入：

3
0 5 10

输出：

5

样例说明

Example 1: put the warehouses at 1 and 10, for a total distance of 0+1+0+1=2. Example 2: put a warehouse at 7, for a total distance of 0. Example 3: either both ends, or one endpoint together with 5, gives the minimum total distance 5.