In the planet Cake, home of the Master Masao, a casino offers a particular game.
There is an array of probabilities *p*_{1}, …, *p*_{2m+1}
for some natural number *m*.
At every moment, a coin has probability *p*_{i} of landing heads when flipped.
If it indeed lands heads, the next time the probability will be *p*_{i+1}.
Otherwise, the probability will be *p*_{i−1}.
The initial “state” is *m*+1.
Before playing, you must decide a number *k* between 1 and *m*+1.
Afterwards, you flip the coin *k* times.
You win if the total number of times the coin landed heads is an odd number.

Given the probabilities of a coin, compute the probability of winning a game assuming an optimal strategy.

**Input**

Input consists of several cases,
each with an odd number *n* followed by *n* probabilities.
Assume *n* < 50.

**Output**

For every case, print the probability of winning with four digits after the decimal point. The input cases have no precision issues.

Public test cases

**Input**

1 0.7 3 1 1 0 3 0.5 0.5 0.5 11 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 3 0.8 0.6 0.3

**Output**

0.7000 1.0000 0.5000 0.9914 0.7400

Information

- Author
- Xavier Martínez
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Setè Concurs de Programacio de la UPC - Semifinal
- Date
- 2009-06-29