Maximizing Score over Marked Intervals

${\rm CYJian}$ gives you a sequence of length N and you are allowed to choose a number x. For your chosen x you mark every element in the sequence which is \(\le x\). Then, the score is defined as the sum of the squares of the lengths of each contiguous segment of marked numbers, i.e. \(\sum_{\text{segment}}(\text{length})^2\). However, the final score is obtained by dividing this sum by the chosen number x, i.e. the score is

[ \text{score} = \frac{\sum_{\text{segment}}(\text{length})^2}{x}, ]

In addition, the number of contiguous marked segments must lie in the interval \([l, r]\) (inclusive). There are T queries. In each query you are given the values of l and r and you are to compute the maximum possible score obtainable by appropriately choosing x satisfying the segment count constraint. If no valid x exists, output -1.

Input is given online.

inputFormat

The first line contains two integers N and T denoting the length of the sequence and the number of queries respectively.

The second line contains N space-separated integers representing the sequence.

Each of the next T lines contains two integers l and r, representing the lower and upper bounds on the number of contiguous marked intervals allowed.

outputFormat

For each query, print a line containing the maximum possible score formatted to 6 decimal places. If no valid choice of x exists, output -1.

sample

5 2
1 2 3 4 5
1 2
2 3

5.000000
-1