随机反馈

Problem Description

你正在参加国际小学生程序设计竞赛的某场区域赛。这场比赛只有一道题，比赛总时长 $n$ 分钟。从第 $1$ 到第 $n$ 分钟，每分钟只能提交一次代码。提交后评测会瞬间完成，也就是这一分钟提交的代码这一分钟就可以知道评测结果，评测结果只有两种：$\texttt{AC}$ 和 $\texttt{WA}$，分别表示通过和没有通过该题。 但这场比赛的评测机出现了一些问题：正确的代码不一定返回 $\texttt{AC}$ 结果，有可能返回 $\texttt{WA}$，具体来说，一份在第 $i$ 分钟提交的正确代码有 $p_i$ 的概率返回 $\texttt{WA}$，有 $1-p_i$ 的概率返回 $\texttt{AC}$。 你在开赛前使用时光机穿越到了比赛结束，偷走了一份正确的代码。通过这次穿越你得知评测机出现了问题，并且知道了所有的 $p_i$ 的取值。为了取得更优秀的成绩，你当然希望你的罚时尽可能小，所以你希望知道你最小的罚时期望是多少。 罚时的定义是你第一次得到 $\texttt{AC}$ 结果的提交时间加上这个提交时间之前的提交次数乘 $20$，当然，如果最后没有通过，罚时视为无穷大。保证 $p_n=0$，即最后一分钟的提交一定正确。

Input

第一行一个正整数 $T$，表示数据的组数。 对于每组数据： 第一行一个整数 $n$（$1\le n\le 10^5$），表示比赛的时长。 接下来一行 $n$ 个整数 $x_1,x_2,\ldots ,x_n$（$0\le x_i\le 1000,x_n=0$），题目中 $p_i=\frac{x_i}{1000}$。 保证所有数据的 $n$ 之和不超过 $5\times 10^5$。

Output

对于每组数据，输出一行一个实数表示最小的罚时期望，当你的答案和正确答案的绝对误差或相对误差小于或等于 $10^{-9}$ 时，你的答案被认为是正确的。

Sample Input

5
3
10 20 0
5
18 12 160 78 0
4
107 471 839 0
6
35 195 237 204 87 0
10
512 585 294 647 13 446 520 447 19 0

Sample Output

1.2142000000
1.3829680000
3.4610000000
1.8750000000
5.3171870000

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（5）