Score : $100$ points

Problem Statement

Let $N$ be a positive odd number.

There are $N$ coins, numbered $1, 2, \ldots, N$. For each $i$ ($1 \leq i \leq N$), when Coin $i$ is tossed, it comes up heads with probability $p_i$ and tails with probability $1 - p_i$.

Taro has tossed all the $N$ coins. Find the probability of having more heads than tails.

Constraints

• $N$ is an odd number.
• $1 \leq N \leq 2999$
• $p_i$ is a real number and has two decimal places.
• $0 < p_i < 1$

Input

Input is given from Standard Input in the following format:

$N$

$p_1$ $p_2$ $\ldots$ $p_N$

Output

Print the probability of having more heads than tails. The output is considered correct when the absolute error is not greater than $10^{-9}$.

3
0.30 0.60 0.80

0.612

The probability of each case where we have more heads than tails is as follows:

• The probability of having $(Coin 1, Coin 2, Coin 3) = (Head, Head, Head)$ is $0.3 \times 0.6 \times 0.8 = 0.144$;
• The probability of having $(Coin 1, Coin 2, Coin 3) = (Tail, Head, Head)$ is $0.7 \times 0.6 \times 0.8 = 0.336$;
• The probability of having $(Coin 1, Coin 2, Coin 3) = (Head, Tail, Head)$ is $0.3 \times 0.4 \times 0.8 = 0.096$;
• The probability of having $(Coin 1, Coin 2, Coin 3) = (Head, Head, Tail)$ is $0.3 \times 0.6 \times 0.2 = 0.036$.

Thus, the probability of having more heads than tails is $0.144 + 0.336 + 0.096 + 0.036 = 0.612$.

1
0.50

0.5

Outputs such as 0.500, 0.500000001 and 0.499999999 are also considered correct.

5
0.42 0.01 0.42 0.99 0.42

0.3821815872