Minimum Sum of Absolute Differences

You are given an array of n positive integers. Rearrange the array such that the sum of the absolute differences between neighboring elements is minimized.

In other words, given an array \(a_1, a_2, \dots, a_n\), rearrange the array to minimize the sum

[ S = \sum_{i=1}^{n-1} |a_i - a_{i+1}|, ]

Your task is to compute and output the minimized sum. The optimal strategy is to sort the array in non-decreasing order.

inputFormat

The first line contains a single integer n (\(2 \le n \le 10^5\)) representing the number of elements in the array.

The second line contains n space-separated positive integers \(a_1, a_2, \dots, a_n\) (each \(1 \le a_i \le 10^9\)).

outputFormat

Output a single integer representing the minimized sum of absolute differences after rearranging the array optimally.

4
10 1 5 8

9