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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
import java.util.LinkedList;

public class Main{
	public class pair implements Comparable<pair> {
		int wt;
		int val;
		double rat;

		pair(int a, int v) {
			wt = a;
			val = v;
			rat = v / wt;
		}

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub
			return (int) (this.rat - o.rat);
		}

	}

	public static long mod = (long) (1e9 + 7);

	public static void main(String[] args) throws IOException {
		Scanner scn = new Scanner(System.in);
		int n = scn.nextInt();
		double head[] = new double[n];
		double tail[] = new double[n];
		for (int i = 0; i < n; i++) {
			head[i] = scn.nextDouble();
			tail[i] = 1 - head[i];
		}
		double dp[][] = new double[n][n + 1];
		dp[0][0] = tail[0];
		dp[0][1] = head[0];
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= n; j++) {
				dp[i][j] = dp[i - 1][j] * tail[i] + (j>0?dp[i - 1][j - 1] * head[i]:0);
			}
		}
		double ans = 0;
		for (int i = n / 2 + 1; i <= n; i++) {
			ans += dp[n - 1][i];
		}
		System.out.println(ans);

	}

	private static int dfs(int sr, HashSet<Integer> hset, int[] dp, ArrayList<Integer>[] g) {
		if (hset.contains(sr)) {
			return dp[sr];
		}
		hset.add(sr);
		int res = -1;
		for (int nei : g[sr]) {
			res = Math.max(res, dfs(nei, hset, dp, g));
		}
		dp[sr] = Math.max(dp[sr], res + 1);
		return dp[sr];

	}

}