Giraffe Abbi's Rolling Keyboard Puzzle

In this problem, you are given n numbers \(a_1, a_2, \dots, a_n\) representing weights. A subinterval (or contiguous subarray) of an interval is defined as any consecutive segment within that interval. The weight of a subinterval is defined as the product of the weights of its elements. Furthermore, the expected weight of an interval is defined as the expected value of the weights when one of its subintervals is chosen uniformly at random.

More formally, for an interval \([l, r]\), let the set of all subintervals be all \([i, j]\) such that \(l \le i \le j \le r\). The number of subintervals is given by \[ \frac{(r-l+1)(r-l+2)}{2}, \] and the expected weight is computed as \[ E = \frac{\sum_{i=l}^{r} \sum_{j=i}^{r} \prod_{k=i}^{j}a_k}{\frac{(r-l+1)(r-l+2)}{2}}. \]

You will be given an array of n numbers and q queries. For each query you are given two integers \(l\) and \(r\). Your task is to compute and output the expected weight over the interval \([l, r]\).

inputFormat

The input begins with two integers n and q \((1 \le n, q \le 10^3)\). The next line contains n numbers \(a_1, a_2, \dots, a_n\), each representing the weight of an element. This is followed by q lines, each containing two integers l and r \((1 \le l \le r \le n)\), representing a query.

outputFormat

For each query, output the expected weight of the subintervals in the segment \([l, r]\) as a floating point number rounded to 6 decimal places.

sample

3 2
1 2 3
1 2
2 3

1.666667
3.666667