Algorithms and Data Structures

Uneven Coin Toss Outcome

You are given n coins, with i-th coin having probability of landing heads when tossed. Your task is to calculate the probability of obtaining more heads than tails after tossing all n coins.

Input

The first line contains a single integer n (1 ≤ n ≤ 2000), representing the number of coins.
The second line contains n real numbers with two decimal places (0 ≤ ≤ 1), representing the probabilities of the i-th coin landing heads.

Output

The program should print a single floating-point number representing the probability of obtaining more heads than tails after tossing all the n coins.

Explanation

Input
Output
3 0.3 0.6 0.4
0.396
1 0.5
0.5
5 0.42 0.01 0.42 0.99 0.42
0.38218

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue