Snack Party

Runalidi has prepared $N$ snacks for Dadas, who is invited to the party. The snacks are numbered from $1$ to $N$.

Dadas considers the snacks in order from $1$ to $N$ and decides once whether to eat each snack. The base probability of eating snack $i$ is $p_i$.

Dadas's fullness is an integer from $0$ to $20$ and is initially $0$. Let $s$ be the fullness immediately before considering snack $i$. Regardless of the earlier outcomes, if they leave the current fullness at $s$, the conditional probability of eating snack $$ is

The probability of not eating it is one minus this value. Immediately after the decision, update the fullness as follows.

• If the snack was eaten, set the fullness to $\min(20,s+1)$.
• Otherwise, set it to $\max(0,s-1)$.

Thus, for a fixed base probability, greater fullness never increases the eating probability, and the actual probability never exceeds the base probability.

There are $Q$ questions, each consisting of two integers $l,r$. Find the expected number of snacks Dadas eats among snacks $l$ through $r$, inclusive, during the entire process.

Every question refers to the same random process that begins with fullness zero and considers snacks $1$ through $N$. Expectations are taken before the process starts. Fullness is not reset at the beginning of a queried interval. Questions do not affect the process, and their order does not change any answer.

The first line contains the number of snacks $N$ and the number of questions $Q$. The second line contains the base probabilities $p_1,p_2,\ldots,p_N$, separated by spaces. Each is written as or , where each is a decimal digit, so exactly two digits appear after the decimal point. Each of the next lines contains the two integers of one question.

Print one answer per line, in question order. An answer is accepted if its absolute or relative error is at most $10^{-6}$.

• $2\leq N\leq100\,000$.
• $1\leq Q\leq100\,000$.
• $0\le p_{}$ ().