Problem: 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}.

Examples

Input

3
0.30 0.60 0.80


Output

0.612


Input

1
0.50


Output

0.5


Input

5
0.42 0.01 0.42 0.99 0.42


Output

0.3821815872

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main {

		
	
	public static void main(String[] args) throws Exception{
		BufferedReader  jk =  new BufferedReader(new InputStreamReader( System.in))  ; 
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)) ; 
		StringTokenizer ana = new StringTokenizer(jk.readLine()) ;
		int n =Integer.parseInt(ana.nextToken()) ; 
		double h[] = new double[n+1] ; 
		ana = new StringTokenizer(jk.readLine()) ;
		for(int i=0 ;i<n ;i++)
		{
			h[i+1]=Double.parseDouble(ana.nextToken());
		}
		double dp[][]= new double[n+1][n+1] ; 
		dp[1][0]= 1-h[1] ; 
		dp[1][1]=h[1]  ;
 		for(int i=2 ; i<=n ;i++)
		{
			double c = h[i] ; 
			dp[i][0]=(1-c)*dp[i-1][0] ; 
			for(int k= 1; k<=i ;k++)
			{
				double res= dp[i-1][k]*(1-c) + dp[i-1][k-1]*c ; 
				dp[i][k] = res ; 
			}
		}
		double res= 0 ; 
		for(int i=(n/2)+1 ; i<=n ;i++)
		{
			res+=(dp[n][i]);
		}
		out.println(res);

		



		out.flush();
	}
}