← 返回题目列表

Codeforces · 235/B

B. 来玩大须吧!

中文机器翻译题面 查看原题

您正在玩一款名为 Osu 的游戏!这是它的简化版本。游戏中有n次点击。每次点击都有两种结果:正确或错误。让我们将正确表示为“O”,将错误表示为“X”,则整个戏剧可以被编码为n个字符“O”和“X”的序列。

使用播放序列,您可以按如下方式计算该播放的得分:对于每个最大连续“O”块,将其长度的平方(字符“O”的数量)添加到得分中。例如,如果您的游戏可以编码为“OOXOOOXXOO”,则存在三个最大的连续“O”块“OO”、“OOO”、“OO”,因此您的分数将为 22 + 32 + 22 = 17。如果游戏中没有正确的点击,则该游戏的分数等于 0。

您知道正确点击第 i 次 (1 ≤ i ≤ n) 次的概率是 pi。换句话说,播放序列中的第 i 个角色有 pi 概率为“O”,1 - pi 为“X”。您的任务是计算您的比赛的预期得分。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 点击次数。第二行包含 n 个空格分隔的实数 p1, p2, ..., pn (0 ≤ pi ≤ 1)。

给定的 pi 中小数点后最多有六位数字。

输出

打印一个实数 — 您的比赛的预期分数。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

示例

输入 #1

3
0.5 0.5 0.5

输出 #1

2.750000000000000

输入 #2

4
0.7 0.2 0.1 0.9

输出 #2

2.489200000000000

输入 #3

5
1 1 1 1 1

输出 #3

25.000000000000000

注意

第一个例子。有 8 种可能的结果。每个的概率为 0.125。

- “OOO” →  32 = 9;
- “OOX” →  22 = 4;
-“OXO” → 12 + 12 = 2;
- “OXX” →  12 = 1;
-“XOO” → 22 = 4;
-“XOX” → 12 = 1;
-“XXO” → 12 = 1;
- “XXX” →  0。

因此预期得分为 $${ \frac { 9 + 4 + 2 + 1 + 4 + 1 + 1 } { 8 } } = 2. 7 5$$