Largest average

Interview

Time limit1sMemory limit64 MB

Summary

Given N grades, repeatedly replace any two numbers with their average until one remains; find the largest possible final value.

Level: Medium5 of 10
Topics: Greedy, Math, Sorting, Implementation
Solved: No attempts yet

Problem

Little Ivica received $N$ math grades and wants to compute their average. He knows that the average of two numbers $a$ and $b$ is $(a+b)/2$ , but he does not yet know what to do with more than two numbers. So he writes the $N$ grades down and repeats the following procedure $N-1$ times.

He picks two of the written numbers and erases them.
He writes down the average of the two numbers he picked.

After $N-1$ steps a single number is left, and Ivica takes it for his average grade. Find the largest number that can be left this way.

Input

The first line contains the integer $N$ ( $1 \le N \le 20$ ).

The $i$ -th of the next $N$ lines contains the integer $X_i$ ( $1 \le X_i \le 5$ ), the $i$ -th grade.

Output

Print the largest number that can be left, rounded to six digits after the decimal point, on one line. Print all six digits, including trailing zeros. If the exact value lies exactly halfway between two six-digit decimals, round up.

Note

Take the grades 1, 3 and 5. At the start, 1, 3 and 5 are written down. In the first step Ivica picks 1 and 3, erases them and writes 2, so 2 and 5 remain. In the second step he writes the average of the two remaining numbers, which is 3.5.

If $N$ is 1, the procedure runs zero times, so the single grade is the answer.

Examples3

Example 1
Input
```
4
2
4
5
2
```
Expected output
```
4.000000
```
Example 2
Input
```
3
5
5
4
```
Expected output
```
4.750000
```
Example 3
Input
```
3
1
3
5
```
Expected output
```
3.500000
```