Expected Time for Beetle to Climb a Tree

A beetle is trying to climb a tree of height n. It starts at the base (height 0). When the beetle attempts to climb from height i-1 to i, it spends one unit of time; however, with probability \(P_i\) it falls all the way back to the base. Given the tree height n and the probabilities \(P_1, P_2, \dots, P_n\), compute the expected time for the beetle to reach the top of the tree.

Note:

• Each climbing attempt always takes 1 unit of time.
• If the attempt from height \(i-1\) to \(i\) fails (with probability \(P_i\)), the beetle returns to height 0 and must start over.
• If it succeeds (with probability \(1-P_i\)), it proceeds to the next step.

Assume that the expected time for the beetle to go from height 0 to height 0 is 0.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(n\) (\(1 \leq n \leq 10^5\)), indicating the height of the tree.
2. The second line contains \(n\) floating point numbers \(P_1, P_2, \dots, P_n\) where each \(P_i\) (\(0 \leq P_i < 1\)) is the probability that the beetle falls to the base when attempting to climb from height \(i-1\) to \(i\).

outputFormat

Output a single floating point number representing the expected time (in time units) to reach the top of the tree. The answer should be printed with at least 6 digits after the decimal point.

sample

1
0.5

2.000000