Description

最近dd喜欢上了一款手机游戏---切水果. 无聊的时候可以打发时间. 但是dd发现自己一开始玩就停不下来了, 每次都玩到天荒地老,海枯石烂...后来dd定了一个规定, 如果当前这次的得分不大于上次的得分,那么就不玩了!

dd玩切水果的得分是一个区间[0,n],每个得分i都有一个相应的概率p[i],满足p[0]+p[1]+...+p[n]=1.0;

给出n和相应的概率,求dd能玩的期望次数.

Input

多组数据.每组数据第一行一个整数n(0<=n<=50000),然后是n+1个浮点数表示相应得分的概率.

Output

输出期望的次数,保留小数点后5位.

Sample

Input

0
1.00000000

1
0.50000000
0.50000000

2
0.20000000
0.30000000
0.50000000

Output

2.00000
2.25000
2.34000

Source: dd