鹦鹉国王正在堆叠 $N$ 个积木以建造一座稳定的塔。只有一种类型的积木，每个积木可以朝上或朝下放置。为了使塔保持稳定，塔必须满足以下性质：对于每个朝上的积木，其上方必须存在一个朝下的积木，使得它们之间的朝上和朝下积木数量相等。类似地，对于每个朝下的积木，其下方必须存在一个朝上的积木，使得它们之间的朝上和朝下积木数量相等。鹦鹉国王以 $p_i$ 的概率将从底部数起第 $i$ 个积木朝上放置，以 $1 - p_i$ 的概率朝下放置。在建好塔之后，他会从中移走最少数量的积木（可能从塔的中间移走），使其变得稳定。求最终得到的塔的期望高度。

鹦鹉国王的塔

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 1000$)，表示鹦鹉国王的塔中的积木数量。

对于 $i = 1, \dots, N$，输入的第 $i + 1$ 行包含一个实数 $p_i$ ($0 \le p_i \le 1$)，表示鹦鹉国王将从底部数起第 $i$ 个积木朝上放置的概率。所有的 $p_i$ 在小数点后最多有八位数字。

输出格式

输出一行，包含稳定塔的期望高度。与真实答案的相对或绝对误差在 $10^{-6}$ 以内的答案将被接受。

样例

输入样例 1

3
0.5
0.5
0.5

输出样例 1

1

输入样例 2

4
0.1
0.2
0.3
0.4

输出样例 2

0.8168