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 ⌊ (1 + 8)/2 ⌋ = 4. We now have 3, 4 and 4, and 3 and 4 are combined, generating a new molecule with weight ⌊ (3 + 4)/2 ⌋ = 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⁹. You can assume that 1 ≤ n ≤ 10⁵.

Output

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

Observation

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