- Time limit: 1.00 s
- Memory limit: 256 MB
A sequence can be approximated as a constant sequence where . The error of such an approximation is .
You are given a sequence and queries. For each query, your task is to approximate a consecutive subsequence of using a constant sequence so that the error is as small as possible.
Input
The first input line contains two integers and : the length of the sequence and the number of queries.
The second input line contains integers that describe the sequence.
Finally, the input contains lines that describe the queries. Each line contains two integers and () that correspond to the subsequence .
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
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 and which refers to the subsequence . The best constant approximation of this sequence is , and the error of this approximation is .