Minimizing the Sum of Absolute Differences

Given an array of n integers, find an integer \(X\) that minimizes the sum of absolute differences \(\sum_{i=1}^{n} |a_i - X|\). It is known that the median minimizes this sum. If n is odd, the median is unique. If n is even, choose the smaller of the two middle elements as \(X\).

The input first contains an integer n (the number of elements), followed by a line of n integers separated by spaces. The output should be a single integer, the optimal \(X\), printed to standard output.

inputFormat

The first line of input contains an integer n (1 ≤ n ≤ 10⁵), the number of elements in the array.
The second line contains n space-separated integers \(a_1, a_2, \dots, a_n\) which may be negative or positive.

outputFormat

Output a single integer \(X\) which minimizes \(\sum_{i=1}^{n} |a_i - X|\). In the case where n is even, output the smaller of the two medians.

1
5

5