Minimizing Absolute Differences

Given an array of integers, find an integer ( k ) that minimizes the sum of absolute differences between each element and ( k ). It is known that the median of the array minimizes the function ( f(k) = \sum_{i=1}^{n} |a_i - k| ). In this problem, you are required to compute the median value by sorting the array and selecting the element at index ( \lfloor \frac{n-1}{2} \rfloor ). Note that if the array length is even, the left middle element is chosen.

inputFormat

The first line contains a single integer ( n ), the number of elements in the array. The second line contains ( n ) space-separated integers representing the array elements.

outputFormat

Output the integer ( k ) that minimizes the sum of absolute differences.## sample

1
42

42