CSES - HIIT Open 2016 - Approximate
  • Time limit: 1.00 s
  • Memory limit: 256 MB

A sequence s1,s2,,sks_1,s_2,\ldots,s_k can be approximated as a constant sequence c1,c2,,ckc_1,c_2,\ldots,c_k where c1=c2==ckc_1=c_2=\cdots=c_k. The error of such an approximation is 1ki=1k(sici)2\frac{1}{k} \sum_{i=1}^k (s_i-c_i)^2.

You are given a sequence x1,x2,,xnx_1,x_2,\ldots,x_n and qq queries. For each query, your task is to approximate a consecutive subsequence of xx using a constant sequence so that the error is as small as possible.

Input

The first input line contains two integers nn and qq: the length of the sequence and the number of queries.

The second input line contains nn integers x1,x2,,xnx_1,x_2,\ldots,x_n that describe the sequence.

Finally, the input contains qq lines that describe the queries. Each line contains two integers aa and bb (1abn1 \le a \le b \le n) that correspond to the subsequence xa,xa+1,,xbx_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

  • 1n,q1051 \le n,q \le 10^5
  • 1xi1001 \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=2a = 2 and b=3b = 3 which refers to the subsequence (x2,x3)=(2,3)(x_2, x_3) = (2,3). The best constant approximation of this sequence is (2.5,2.5)(2.5, 2.5), and the error of this approximation is (0.52+0.52)/2=0.25(0.5^2 + 0.5^2)/2 = 0.25.