Minimum Absolute Differences Sum

Given an array of integers, compute the sum of absolute differences between each element and the median of the array. Note that if the array has an even number of elements, you should take the median as the left middle element after sorting the array.

The median minimizes the sum of absolute deviations. In other words, if the sorted array is \(a_1, a_2, \ldots, a_n\) and \(m\) is chosen as the median, then the objective is to compute:

$$ S = \sum_{i=1}^{n} |a_i - m| $$

Your task is to implement a program that reads the array from standard input, computes the sum as described, and prints the result to standard output.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the number of elements in the array. The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) where \(|a_i| \le 10^9\).

outputFormat

Output a single integer — the minimum sum of absolute differences between each element and the median of the array.

5
1 2 3 4 5

6