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:
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long long ll;
const int mod = 1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it, len;
	fastio() {it=len=0;}
	inline char get()
	{
		if (it<len) return s[it++]; it=0;
		len=fread(s, 1, 100000, stdin);
		if (len==0) return EOF; else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while (c==' '||c=='\n') c=get();
		if (it>0) it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0; bool ng=0; char c; c=_buff.get();
	while (c!='-'&&(c<'0'||c>'9')) c=_buff.get();
	if (c=='-') ng=1, c=_buff.get();
	while (c>='0'&&c<='9') r=r*10+c-'0', c=_buff.get();
	return ng?-r:r;
}
template <class T> inline void putnum(T x)
{
	if (x<0) putchar('-'), x=-x;
	register short a[20]={}, sz=0;
	while (x) a[sz++]=x%10, x/=10;
	if(sz==0) putchar('0');
	for (int i=sz-1; i>=0; i--) putchar('0'+a[i]);
}
inline char getreal() {char c=_buff.get(); while (c<=32) c=_buff.get(); return c;}
ll qpow(ll x, ll k) {return k==0? 1: 1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
const int maxn = 100111;
const double mn = 1e20;

int n;
double a[maxn], dp[maxn];
struct data
{
	double prod, sum;
	data(double A=0, double B=0) : prod(A), sum(B) {}
	data operator + (const data &t) const
	{
		return data(prod*t.prod, t.sum+sum*t.prod); 
	}
}D[maxn][20];
data query_data(int l, int r)
{
	data ret(1, 0);
	for (int i=19; i>=0; i--)
	{
		if (r-(1<<i)>=l-1)
		{
			ret = D[r][i]+ret;
			r -= 1<<i;
		}
	}
	return ret;
}
int get_point(int x, int y)
{
//	cerr<<"get_point:"<<x<<","<<y<<endl;
	data dx = query_data(x+1, y), dy(1, 0);
	int pt = y;
	for (int i=19; i>=0; i--)
	{
		if (pt+(1<<i)<=n)
		{
			data ndx = dx+D[pt+(1<<i)][i];
			data ndy = dy+D[pt+(1<<i)][i];
			if (dp[x]+ndx.sum<dp[y]+ndy.sum)
			{
				pt += 1<<i;
				dx = ndx;
				dy = ndy;
			}
		}
	}
	return pt+1;
}
void solve()
{
	vector<int> v, pt;
	v.PB(0);
	int it = 0;
	for (int i=1; i<=n; i++)
	{
		while (it+1<v.size()&&i>=pt[it]) it++;
//		for (auto x : v) cerr<<x<<" "; cerr<<endl;
//		for (auto x : pt) cerr<<x<<" "; cerr<<endl;		
//		cerr<<v[it]<<"->"<<i<<endl;
		dp[i] = dp[v[it]]+query_data(v[it]+1, i).sum+1;
		while (pt.size()>0&&get_point(v.back(), i)<=pt.back()) v.pop_back(), pt.pop_back();
		it = min(it, int(v.size())-1);
		pt.PB(get_point(v.back(), i));
		v.PB(i);
	}
}
int main()
{
	while (true)
	{
		scanf("%d", &n);
		if (n==0) break;
		for (int i=1; i<=n; i++) scanf("%lf", &a[i]), a[i] = 1.0/a[i];
		for (int i=1; i<=n; i++)
		{
			D[i][0] = data(a[i], a[i]);
			for (int j=1; j<20; j++)
			{
				if (i>=(1<<j)) D[i][j] = D[i-(1<<j-1)][j-1]+D[i][j-1]; 
			}
		}
		/*
		for (int i=1; i<=n; i++)
		{
			dp[i] = 1e9;
			for (int j=i; j>=1; j--)
			{
				dp[i] = min(dp[i], dp[j-1]+query_data(j, i).sum+1);
			}
		}*/
		solve();
		printf("%.10lf\n", dp[n]-1);
	}
	return 0;
}