G. Scoring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Monocarp is participating in a competition. There are $$$n$$$ judges evaluating the participants; the score given by each of them is an integer between $$$1$$$ and $$$10^{9}$$$, inclusive (the bigger it is, the better for the participant).

According to the rules of the competition, the final score of the participant is an integer, which is calculated based on the list of $$$n$$$ integers given by the judges, as follows:

  • let $$$x$$$ be the minimum of the scores in the list, and $$$y$$$ be the maximum of the scores in the list. Both $$$x$$$ and $$$y$$$ are removed from the list (note that if there are multiple occurrences of the minimum/maximum in the list, only one of them is removed); then, the number $$$\frac{x + y}{2}$$$, rounded down to the nearest integer, is added to the list.

This operation is performed $$$n - 1$$$ times, after which, the list contains only one number. The remaining integer is the final score of the participant.

You have to calculate Monocarp's final score according to these rules, based on the score he received from each judge.

Input

The first line contains one integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of judges.

The second line contains the sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — the scores given by the judges.

Output

Print one integer — the final score calculated according to the rules of the competition.

Examples
Input
5
3 6 1 9 1
Output
3
Input
8
12 12 40 30 20 24 21 13
Output
20
Input
3
100 100 100
Output
100
Note

The sorted list of the scores in the first example is $$$[1, 1, 3, 6, 9]$$$.

During the first operation, $$$x = 1$$$, $$$y = 9$$$. These integers are removed, and $$$\frac{1 + 9}{2} = 5$$$ is added. So, the current list is $$$[1, 3, 5, 6]$$$.

During the second operation, $$$x = 1$$$, $$$y = 6$$$. These integers are removed, and $$$\frac{1 + 6}{2} = 3$$$ (rounded down) is added. So, the current list is $$$[3, 3, 5]$$$.

During the third operation, $$$x = 3$$$, $$$y = 5$$$. These integers are removed, and $$$\frac{3 + 5}{2} = 4$$$ is added. So, the current list is $$$[3, 4]$$$.

During the fourth operation, $$$x = 3$$$, $$$y = 4$$$. These integers are removed, and $$$\frac{3 + 4}{2} = 3$$$ (rounded down) is added. So, the current list is $$$[3]$$$.

The final score is $$$3$$$, since it is the only element of the resulting list.