1010 - 动态规划:期望DP:朝上或朝下

通过次数

1

提交次数

38

Time Limit : 1 秒
Memory Limit : 256 MB

有这么个玩法: 在每一轮中,孩子们将手朝上(白色)或者朝下(黑色)。 如果所有的孩子做出相同的选择,只有一个例外,那么那个例外的孩子将会被淘汰。 游戏重复进行,直到只剩下两个孩子停止。 每个孩子有一个固定的概率独立选择是否将手朝上。 给定n个孩子的概率,请输出游戏期望回合数是多少。

Input

第一行为正整数n,n不超过20,表示孩子数量。 接下来n行,每行一个数字pi表示孩子i的概率,0.1≤pi≤0.9。

Output

输出一个数字表示期望回合数。 注意:输出结果与标准结果的绝对误差或者相对误差小于10^-6即视为正确。

Examples

Input

3
0.5
0.5
0.5

Output

1.3333333

Input

5
0.1
0.3
0.5
0.7
0.9

Output

7.4752846