Planet Cake P12956

In the planet Cake, home of the Master Masao, a casino offers a particular game. There is an array of probabilities $p_1, \ldots, 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.