Minimize Sum of Absolute Differences

Given a sorted array of n integers, your task is to choose an element x from the array that minimizes the function

$$S(x)=\sum_{i=1}^{n}|x-a_i|$$

If there are multiple candidates that yield the minimal sum, select the smallest one.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains an integer n, representing the number of elements in the array.
• The second line contains n space-separated integers in non-decreasing order.

outputFormat

Output a single integer via standard output (stdout) which is the element from the array that minimizes the sum of absolute differences. In case of multiple solutions, output the smallest one.

5
1 2 3 4 5

3