D. Professor R's. Median
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In mathematical statistics there is such a thing as the median of a series of numbers. The median of a series of numbers is a number in the middle of an ascending series of numbers if the number of figures is odd. If the number of figures in the row is even, then the median of the row is the half-sum of the two numbers in the middle of the ascending order.

But in Yaroslavl State University they are not lazy — scholars have invented a new concept — the median of Professor R. Let's define it. The median of Professor R. of a series of numbers is the number in this series closest to the half-sum of the minimum and maximum figures, and if there are several such numbers, the minimum in value is selected from them. Your task is to find Professor R's median in a given series of numbers.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of elements.

The second line contains n space-separated integers ai — elements of a series of numbers (|ai| ≤ 2·109).

Output

In a single line type The median of Professor R. value.

Examples
Input
5
1 1 1 1 1
Output
1
Input
3
1 2 3
Output
2