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<bits/stdc++.h>
using namespace std;
int n;
double p[111111],dp[111111];
deque<int> q,qq;
struct node
{
	double s,p;
	node()
	{
		p=1.00;
		s=0.00;
	}
	node operator + (const node &u) const
	{
		node res;
		res.s=s+p*u.s;
		res.p=p*u.p;
		return res;
	}
}f[111111][22],cx,cy,nx,ny;
node cost(int l,int r)
{
	node res;
	for (int i=18;i>=0;i--)
	{
		if (r-(1<<i)+1>=l)
		{
			res=res+f[r][i];
			r-=(1<<i);
		}
	}
	return res;
}
int get_ver(int x,int y)//get the first point that dp[x]+cost(x+1,i)>=dp[y]+cost(y+1,i),x<y
{
	cx=cost(x+1,y);cy=node();
	int ans=y;
	for (int i=18;i>=0;i--)
	{
		if (ans+(1<<i)<=n)
		{
			nx=f[ans+(1<<i)][i]+cx;ny=f[ans+(1<<i)][i]+cy;
			if (dp[x]+nx.s<dp[y]+ny.s)
			{
				ans+=(1<<i);
				cx=nx;cy=ny;
			}
		}
	}
	return ans+1;
}
int main()
{
	while(scanf("%d",&n)==1)
	{
		if (!n) break;
		for (int i=1;i<=n;i++) scanf("%lf",&p[i]);
		for (int i=1;i<=n;i++) f[i][0].s=f[i][0].p=1.00/p[i];
		for (int i=1;i<=18;i++)
		{
			for (int j=(1<<i);j<=n;j++)
			{
				f[j][i]=f[j][i-1]+f[j-(1<<(i-1))][i-1];
			}
		}
		q.clear();qq.clear();
		q.push_back(0);qq.push_back(0);
		dp[0]=0.00;
		for (int i=1;i<=n;i++)
		{
			while(q.size()>1 && qq[1]<=i) 
			{
				q.pop_front();
				qq.pop_front();
			}
			dp[i]=dp[q.front()]+cost(q.front()+1,i).s+1.00;
			while(q.size()>1 && get_ver(q.back(),i)<=qq.back())
			{
				q.pop_back();qq.pop_back();
			}
			qq.push_back(get_ver(q.back(),i)); 
			q.push_back(i); 
		} 
		printf("%.10lf\n",dp[n]-1.00);
	}
	return 0;
}