Evolution of molecules X74560

In an experiment with $n$ molecules of several integer weights, a curious phenomenon has been detected: repeatedly, the lightest and the heaviest molecules are combined, they disappear, and generate a new molecule with the average of the two weights (rounded down if necessary). The process finishes when only one molecule exists.

For example, if the initial weights are 1, 3, 4 and 8, first of all 1 and 8 are combined and generate a molecule with weight $\lfloor (1 + 8)/2 \rfloor = 4$. We now have 3, 4 and 4, and 3 and 4 are combined, generating a new molecule with weight $\lfloor (3 + 4)/2 \rfloor = 3$. Now we only have 3 and 4, which are combined to generate one with weight 3, which is the final result.

Write a program that efficiently simulates this process and writes the weight of the last molecule.

Input

The input consists of several cases. Each case begins with the number of molecules $n$, followed by $n$ weights, which are integers between 1 and $10^9$. You can assume that $1 \le n \le 10^5$.

Output

For each case, write the weight of the last molecule.

Observation

We advise you not to use multisets to solve this problem.