Representative Natural Number

Given several natural numbers, choose one natural number that best represents them.

For a chosen natural number X, compute the absolute difference between X and each given number, then add all of those differences. A representative natural number is a value of X that makes this total as small as possible.

Consider the numbers 4, 3, 2, 2, 9, and 10. If X is 3, the total difference is 16, and if X is 4, the total difference is also 16. Both values minimize the total, so the representative natural numbers are 3 and 4. When there is more than one representative natural number, choose the smallest one.

Write a program that finds the representative natural number of the given numbers.

The first line contains the number of natural numbers N. N is between 1 and 20,000, inclusive.

The second line contains N natural numbers separated by spaces. Each number is between 1 and 10,000, inclusive.

Print the representative natural number on the first line. If there is more than one such number, print the smallest one.