M. Mean Absolute Deviation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rami loves many branches of mathematics. But, if there is an exception, it must be statistics.

For usual mathematical problems, he will devote his time to understand the structure of the problem and gain intuition, but for statistics, he will forward it to a friend.

But when Statistics and Competitive Programming intersects, that friend should be Yessine who received a recent email from Rami:

Dear Yessine

Today, I have received an interesting problem that I hope that you will like.

Spoiler Alert: This problem is difficult, even for you ☺:

Given $$$n$$$ reals $$${x}=[x_1,\dots,x_n],$$$ I challenge you to calculate the mean absolute deviation $$$\delta({x})$$$ (MAD): $$$$$$ \delta({x})=\frac{1}{n}\sum_{i=1}^n\lvert x_i-\mu({x})\rvert$$$$$$ $$$$$$ \texttt{where: } \mu({x})=\frac{1}{n}\sum_{i=1}^nx_i \texttt{ is the mean} $$$$$$ Now, to make things worse, I challenge you to redo the calculation for $$$q$$$ subarrays of $$${x}:{x_{[l_1,r_1]}},\dots,{x_{[l_q,r_q]}}$$$:

$$$$$$ \texttt{Find }\delta({x}_{[l_i,r_i]}) \texttt{ for each }i\in\{1,\dots,q\}\\ $$$$$$

Here is the list of constraints:

$$$1\leq n \leq 10^5$$$$$$1\leq q \leq 10^5$$$$$$1\leq l_i \leq r_i \leq n$$$

Best Regards,

Rami.

Yessine was mad that such an easy problem was given to him, or so he thought until reading the constraints.

Now, neither Rami nor Yessine are capable of solving this problem, so they both request your help.

Input

1. The first line contains two integers $$$1\leq n,q \leq 10^5$$$ representing the size of the array and the number of queries

2. The second line contains $$$n$$$ reals $$$x_1,\dots,x_n$$$ representing the values of the array $$$1 \le x_i \le 10^9$$$

3. Each of the following $$$q$$$ lines contains $$$2$$$ integers $$$l,r$$$ with $$$1 \leq l,r \leq n$$$ representing the considered subarray $$$x_{[l,r]}$$$

Output

$$$q$$$ reals, with the $$$i^\text{th}$$$ line representing the mean absolute deviation of the subarray $$$x_{[l_i,r_i]}$$$

Examples
Input
5 7
0 10 0 1 3
1 3
2 4
2 2
4 5
3 5
1 2
3 4
Output
4.444444
4.222222
0.000000
1.000000
1.111111
5.000000
0.500000
Input
5 7
4 3 0 5 8
3 4
2 2
1 4
3 5
2 3
2 3
3 4
Output
2.500000
0.000000
1.500000
2.888889
1.500000
1.500000
2.500000
Note

Yessine received a clarifying mail from Rami:

To Yessine

Well, I accidently omitted the definition of the mean absolute deviation of a subarray, here is it with a little example:

- The mean of the subarray $$${x}_{[l_i,r_i]}$$$ is : $$$$$$ \mu({x}_{[l_i,r_i]}) = \frac{1}{r_i-l_i+1}\sum_{j=l_i}^{r_i} x_j$$$$$$

- The mean absolute deviation of the subarray $$${x}_{[l_i,r_i]}$$$ is : $$$$$$\delta({x}_{[l_i,r_i]})=\frac{1}{r_i-l_i+1}\sum_{j=l_i}^{r_i} \lvert x_j-\mu({x}_{[l_i,r_i]}) \rvert$$$$$$

- For a little example, consider the array $$$x=[0,10,0,1,3]$$$ and the query $$$l=1,r=3.$$$ We have $$$x_{[1,3]}=[0,10,0]$$$. The mean of the subarray is $$$\mu(x_{[1,3]})=\frac{10}{3}$$$ and the MAD is: $$$$$$ \delta({x}_{[1,3]})=\frac{1}{3}\sum_{j=1}^{3} \lvert x_j-\mu({x}_{[1,3]}) \rvert = \frac{\lvert 0-\tfrac{10}{3}\rvert+\lvert 10-\tfrac{10}{3}\rvert+\lvert 0-\tfrac{10}{3}\rvert}{3} = \frac{\tfrac{10}{3}+\tfrac{20}{3}+\tfrac{10}{3}}{3} = \frac{40}{9} \approx 4.44444 $$$$$$

Good Luck,

Rami.