A sequence $s_1,s_2,\ldots,s_k$ can be approximated as a constant sequence $c_1,c_2,\ldots,c_k$ where $c_1=c_2=\cdots=c_k$. The error of such an approximation is $\frac{1}{k} \sum_{i=1}^k (s_i-c_i)^2$.
You are given a sequence $x_1,x_2,\ldots,x_n$ and $q$ queries. For each query, your task is to approximate a consecutive subsequence of $x$ using a constant sequence so that the error is as small as possible.
Input
The first input line contains two integers $n$ and $q$: the length of the sequence and the number of queries.
The second input line contains $n$ integers $x_1,x_2,\ldots,x_n$ that describe the sequence.
Finally, the input contains $q$ lines that describe the queries. Each line contains two integers $a$ and $b$ ($1 \le a \le b \le n$) that correspond to the subsequence $x_a,x_{a+1},\ldots,x_b$.
Output
For each query, output the smallest possible error (rounded to exactly 6 decimal digits) when the subsequence is approximated using a constant sequence.
Constraints
- $1 \le n,q \le 10^5$
- $1 \le x_i \le 100$
Example
Input:
8 3
1 2 3 3 3 3 3 1
2 3
4 6
1 8
Output:
0.250000
0.000000
0.734375
Explanation: The first query is $a = 2$ and $b = 3$ which refers to the subsequence $(x_2, x_3) = (2,3)$. The best constant approximation of this sequence is $(2.5, 2.5)$, and the error of this approximation is $(0.5^2 + 0.5^2)/2 = 0.25$.