Representative Natural Number

Interview

Time limit1sMemory limit128 MB

Summary
Find the smallest integer minimizing the sum of absolute differences to a list of numbers, which is the lower median.
Level

Easy3 of 10

Topics
Sorting, Math, Array
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

Examples1

  1. Example 1

    Input
    6
4 3 2 2 9 10
    Expected output
    3