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++