Binary Seating

Interview

Time limit1sMemory limit512 MB

Summary

Each of n students independently picks room 0 or room 1 with equal probability; compute the expected maximum finish time among the students who pick room 1.

Level: Medium6 of 10
Topics: Probability, Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

By accident, two rooms (room $0$ and room $1$ ) got booked for the theoretical exam of the B++ Applied Programming Course and both were communicated to the students. Now students might go to either of the rooms, and as a student assistant your job is to supervise room $1$ . Since you assisted all these students during the course, you know how much time each student will need to finish the exam. Already before the exam you are eager to go home, but you can only leave when all of the students in your examination room have finished. You assume that every student chooses one of the exam rooms with equal probability, independent of the other students. After how much time do you expect to be able to leave?

Input

The input consists of:

A line with an integer $n$ ( $1 \leq n \leq 40$ ), the number of students.
A line with $n$ integers $t_1, \ldots, t_n$ ( $1 \leq t_i \leq 1000$ ): $t_i$ is the time it takes for the $i$ th student to finish the exam and leave.

Output

Output the expected time before you can leave. Your answer should have an absolute or relative error of at most $10^{-6}$ .

Examples3

Example 1
Input
```
2
2 3
```
Expected output
```
2
```
Example 2
Input
```
5
1 4 5 2 3
```
Expected output
```
4.03125
```
Example 3
Input
```
5
2 1 1 1 1
```
Expected output
```
1.46875
```