N sticks are arranged in a row, and their lengths are a1,a2,...,aNa1,a2,...,aN.
There are QQ querys. For ii-th of them, you can only use sticks between lili-th to riri-th. Please output the maximum circumference of all the triangles that you can make with these sticks, or print −1−1 denoting no triangles you can make.
Input
There are multiple test cases.
Each case starts with a line containing two positive integers N,Q(N,Q≤105)N,Q(N,Q≤105).
The second line contains NN integers, the ii-th integer ai(1≤ai≤109)ai(1≤ai≤109) of them showing the length of the ii-th stick.
Then follow QQ lines. ii-th of them contains two integers li,ri(1≤li≤ri≤N)li,ri(1≤li≤ri≤N), meaning that you can only use sticks between lili-th to riri-th.
It is guaranteed that the sum of NNs and the sum of QQs in all test cases are both no larger than 4×1054×105.
Output
For each test case, output QQ lines, each containing an integer denoting the maximum circumference.