Problem M
Mysterious Tower

The Parakeet King’s tower

The Parakeet King is stacking $N$ blocks to make a stable tower. There is only one type of block, and each block can be placed face-up or face-down. In order for the tower to be stable, the tower must satisfy the following property: for every face-up block, there exists a face-down block above it such that the numbers of face-up and face-down blocks between them are equal. Similarly, for every face-down block, there exists a face-up block below it such that the number of face-up and face-down blocks between them are equal. The Parakeet King places the $i$th block from the bottom of the tower face up with probability $p_i$ and face down with probability $1-p_i$. After building his tower, he removes the minimum number of blocks from it (possibly from the middle of the tower) to make it stable. Find the expected height of the resulting tower.

Input

Line $1$ of the input contains a single integer $N \: (1 \leq N\leq 1000)$, denoting the number of blocks in the Parakeet King’s Tower. For $i=1,\ldots ,N$, line $i+1$ of the input contains a single real number $p_i \: (0\leq p_i\leq 1)$, denoting the probability the Parakeet King places the $i$th block from the bottom of the tower face up. All $p_i$’s have at most eight digits after the decimal point.

Output

Output one line containing the expected height of the stable tower. Answers within a relative or absolute error of $10^{-6}$ will be accepted.

3
0.5
0.5
0.5

1

4
0.1
0.2
0.3
0.4

0.8168