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 PYTHON):

Solution:
import sys

#TODO: Find a better DP solution
#Current is just a recursive solution
#Time complexity of recursive solutions?

class Solution(object):
	def __init__(self):
		self.n = 0
		self.p = []
		self.result = 0

	def readInput(self):
		self.n = int(sys.stdin.readline())
		a = sys.stdin.readline().split()
		for i in xrange(self.n):
			self.p.append(float(a[i]))
		#print self.p

	def coinTossRec(self, idx, tail_count, prob):
		if idx == self.n - 1:
			#last index
			self.result += (prob * self.p[idx])
			if tail_count != 0:
				#Check for head
				self.result += (prob * (1-self.p[idx]))
		else:
			self.coinTossRec(idx+1, tail_count, prob * self.p[idx])
			if tail_count != 0:
				self.coinTossRec(idx+1, tail_count-1, prob * (1-self.p[idx]))

	def coinTossIter(self):
		dp = [0] * (self.n + 1) #i is the probability of i heads so far
		dp[0] = 1
		for i in xrange(self.n):
			p_heads = self.p[i]
			for j in xrange(i+1, -1, -1):
				if j == 0:
					dp[j] = dp[j] * (1 - p_heads)
				else:
					dp[j] = dp[j-1] * p_heads + dp[j] * (1- p_heads)
		ans = 0
		for i in xrange((self.n//2) + 1, self.n+1):
			ans += dp[i]

		print ans

	def coinToss(self):
		tail_count = self.n // 2 if self.n %2 == 1 else self.n //2 - 1
		self.coinTossRec(0, tail_count, 1)
		print self. result		


if __name__ == '__main__':
	s = Solution()
	s.readInput()
	s.coinTossIter()