Somme minimale après permutation des éléments dans une tranche

Go Hard slices

Tâche «Somme minimale après permutation des éléments dans une tranche»

Étant donné une tranche (slice) d'entiers de longueur N. Il est permis de réarranger les éléments de la tranche de manière arbitraire. Il faut trouver la somme minimale possible des modules des différences entre éléments adjacents après le réarrangement, c'est-à-dire minimiser la somme |a[i] - a[i+1]| pour i allant de 0 à N-2. Affichez cette somme minimale.

Format d\ entrée

Première ligne : un entier N (1 ≤ N ≤ 10^5). Deuxième ligne : N entiers, ne dépassant pas 10^9 en valeur absolue, séparés par des espaces.

Format de sortie

Un seul entier — la somme minimale possible des modules des différences entre éléments adjacents.

Exemples

Exemple 1

ENTRÉE

5
10 0 5 0 10

SORTIE

40

Exemple 2

ENTRÉE

a3b2c

SORTIE

aaabbc

main.go