Problem: Problem Statement

Infinite Chronicle -Princess Castle- is a simple role-playing game. There are $n + 1$ checkpoints, numbered $0$ through $n$, and for each $i = 1, 2, \ldots, n$, there is a unique one-way road running from checkpoint $i - 1$ to $i$. The game starts at checkpoint $0$ and ends at checkpoint $n$. Evil monsters will appear on the roads and the hero will have battles against them. You can save your game progress at any checkpoint; if you lose a battle, you can restart the game from the checkpoint where you have saved for the last time. At the beginning of the game, the progress is automatically saved at checkpoint $0$ with no time.

Rabbit Hanako is fond of this game and now interested in speedrunning. Although Hanako is an expert of the game, she cannot always win the battles because of random factors. For each $i$, she estimated the probability $p_i$ to win all the battles along the road from checkpoint $i - 1$ to $i$. Everytime she starts at checkpoint $i - 1$, after exactly one miniutes, she will be at checkpoint $i$ with probability $p_i$ and where she saved for the last time with probability $1 - p_i$.

What puzzles Hanako is that it also takes one minute (!) to save your progress at a checkpoint, so it might be a good idea to pass some checkpoints without saving in order to proceed quickly. The task is to compute the minimum possible expected time needed to complete the game.

Input

The input consists of multiple datasets. The number of datasets is no more than $50$. Each dataset has two lines: the first line contains an integer $n$ ($1 \le n \le 10^5$), representing the number of roads, and the second line contains $n$ numbers $p_1, p_2, \ldots, p_n$ ($0 \lt p_i \le 1$), representing the winning probabilities. Each $p_i$ has exactly two digits after the decimal point. The end of input is denoted as a line containing only a single zero.

Output

For each dataset, display the minimum expected time in minutes with a relative error of at most $10^{-8}$ in a line.

Sample Input


2
0.50 0.40
2
0.70 0.60
4
0.99 1.00 1.00 0.01
0

Output for the Sample Input


5.5000000000
4.0476190476
104.0101010101





Example

Input

2
0.50 0.40
2
0.70 0.60
4
0.99 1.00 1.00 0.01
0


Output

5.5000000000
4.0476190476
104.0101010101

Solution (in CPP):

Solution:
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
//#define T_ int
using namespace std;
//struct bit{T_ arr[1000005];int lowbit(int x){return x&(-x);}void add(int x,T_ y){for (int i=x;i<=n;i+=lowbit(i)) arr[i]+=y;}T_ query(int x){T_ s=0;for (int i=x;i>0;i-=lowbit(i)) s+=arr[i];return s;}};
//struct seg{struct treedot{int l,r;T_ sum,add;void update(T_ x){sum+=(r-l+1)*x; add+=x;}}c[800005];void pushdown(int id){if (c[id].add){c[id*2].update(c[id].add);c[id*2+1].update(c[id].add);c[id].add=0;}}void pushup(int id){c[id].sum=c[id*2].sum+c[id*2+1].sum;}void build(int id,int l,int r){if (l>r) return;c[id].l=l;c[id].r=r;c[id].sum=0;c[id].add=0;if (l==r) c[id].sum=0;else{int mid=l+(r-l)/2;build(id*2,l,mid);build(id*2+1,mid+1,r);pushup(id);}}void update(int id,int le,int ri,T_ x){if (le>c[id].r||ri<c[id].l) return;if (le<=c[id].l&&c[id].r<=ri) c[id].update(x);else{pushdown(id);update(id*2,le,ri,x);update(id*2+1,le,ri,x);pushup(id);}}T_ query(int id,int le,int ri){if (ri<c[id].l||c[id].r<le) return 0;if (le<=c[id].l&&c[id].r<=ri) return c[id].sum;T_ ans=0;pushdown(id);ans+=query(id*2,le,ri);ans+=query(id*2+1,le,ri);pushup(id);return ans;}};
//struct bit_2d{T_ a[2005][2005];int lowbit(int x){return x&(-x);}void add(int x,int y,T_ z){int i,j;for (i=x;i<=2000;i+=lowbit(i)){for (j=y;j<=2000;j+=lowbit(j)){a[i][j]+=z;}}}T_ query(int x,int y){int i,j;T_ s=0;for (i=x;i;i-=lowbit(i)){for (j=y;j;j-=lowbit(j)){s+=a[i][j];}}return s;}T_ query(int x,int y,int xx,int yy){return query(xx,yy)-query(x-1,yy)-query(xx,y-1)+query(x-1,y-1);}};
int n,m,i,j,t,qx[100005],ql,qr,len[100005];
double dp[100005],p[100005]; 
int main()
{
	while (scanf("%d",&n)&&n)
	{
		m=0;
		fz1(i,n)
		{
			scanf("%lf",&p[++m]);len[m]=1;
			if (m>1&&p[m]>0.995&&p[m-1]>0.995){
				m--;len[m]++;
			}
		}
		fz1(i,m)
		{
			double pro=1,tim=0;
			dp[i]=1e18;
			for (j=i;j>=i-100&&j>=0;j--){
				dp[i]=min(dp[i],dp[j]+tim+1);
				pro/=p[j];
				tim+=pro*len[j];
			}
		}
		printf("%.23lf\n",dp[m]-1);
	}
	return 0;
}