Knockout Tournament

Laura is organising a knockout tournament, and her friend Dale takes part in it. Laura wants to arrange the games so that the probability of Dale winning the tournament is as large as possible. She does not know how to do it, so she asked you for help. You were about to refuse to cooperate with such a deplorable act, but then you realised that it is a very nice puzzle.

When the number of players is a power of two, the tournament is defined recursively: the players are split, in line-up order, into two groups of equal size, each group plays its own knockout tournament, and then the winners of both tournaments play each other. Once a player loses, they are out of the tournament.

When the number of players is not a power of two, some of the last players in the starting line-up advance from the first round automatically so that the number of players left in the second round is a power of two. In the first round the players at the front of the line-up are paired two by two, and the first-round winners followed by the players who advanced automatically, in line-up order, form the tournament from the second round on. Figure K.1 shows an example.

Figure K.1: A tournament tree with 5 players. Players C, D, and E advance from the first round automatically.

Every player has a rating that indicates their strength. A player with rating $a$ wins a game against a player with rating $b$ with probability $a/(a+b)$, independently of any previous games.

Laura, as the organiser, can order the starting line-up of players in any way she likes. What is the maximum probability of Dale winning the tournament?

The input consists of:

• One line with an integer $n$ ($2 \le n \le 4096$), the total number of players.
• $n$ lines, each with an integer $r$ ($1 \le r \le 10^5$), the rating of a player. The first rating given is Dale's rating.

Output the maximum probability of Dale winning the tournament under the most favourable line-up, rounded to nine decimal places and printed with exactly nine digits after the decimal point. For example, a probability of $1/8$ is printed as 0.125000000.