Minimum sum after rearranging elements in a slice

Go Hard slices

Task «Minimum sum after rearranging elements in a slice»

Given an integer slice of length N. It is allowed to rearrange the elements of the slice in any order. It is necessary to find the minimum possible sum of absolute differences of adjacent elements after rearrangement, that is, minimize the sum |a[i] - a[i+1]| for i from 0 to N-2. Output this minimum sum.

Input Format

First line: an integer N (1 ≤ N ≤ 10^5). Second line: N integers, each not exceeding 10^9 in absolute value, separated by spaces.

Output Format

One integer — the minimum possible sum of absolute differences of adjacent elements.

Examples

Example 1

INPUT

5
10 0 5 0 10

OUTPUT

40

Example 2

INPUT

a3b2c

OUTPUT

aaabbc

main.go