Minimize the Absolute Sum of Differences

You are given a list of n integers. Your task is to choose an integer x such that the sum of absolute differences between x and all elements of the list is minimized. Formally, you need to minimize the value:

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

If more than one integer gives the same minimum sum, output the smallest such x. It is a well-known fact that the median of the list minimizes the sum of absolute deviations. When the list contains an even number of elements, choose the smaller of the two middle elements.

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 10⁵), the number of elements in the list. The second line contains n space-separated integers, each representing an element of the list. Each integer is between -10⁹ and 10⁹, inclusive.

outputFormat

Output a single integer x which minimizes the sum \(\sum_{i=1}^{n} |x - a_i|\). If multiple values yield the same sum, output the smallest one.

## sample

3
1 2 3

2

</p>