Maximum Sum of Absolute Differences

You are given n cards, with numbers written on them. The number on the i-th card is \(a_i\). Your task is to shuffle the cards to maximize the sum of the absolute differences between consecutive cards. In other words, if after shuffling the sequence of numbers becomes \(b_1, b_2, \dots, b_n\), you need to maximize the quantity

For example, suppose there are 4 cards with numbers \([1, 2, 3, 4]\). The sum for the order \([4, 3, 2, 1]\) is $$|4-3| + |3-2| + |2-1| = 1+1+1 = 3,$$

while for the order ([2, 4, 1, 3]) it is

Since (7 > 3), the order ([2, 4, 1, 3]) is considered "more shuffled". You need to compute the maximum value of (S) over all possible orders.

inputFormat

The first line contains a single integer \(n\) (the number of cards). The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the numbers on the cards.

It is guaranteed that \(n\) is small enough to allow a solution that checks all permutations.

outputFormat

Output a single integer — the maximum possible sum \(S = \sum_{i=1}^{n-1} |b_{i+1} - b_i|\) that can be achieved by reordering the cards.

sample

4
1 2 3 4

7