Problem Description

$N$ sticks are arranged in a row, and their lengths are $a_1, a_2, ... , a_N$.

There are $Q$ querys. For $i$-th of them, you can only use sticks between $l_i$-th to $r_i$-th. Please output the maximum circumference of all the triangles that you can make with these sticks, or print $-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 \leq 10^5)$.

The second line contains $N$ integers, the $i$-th integer $a_i(1 \leq a_i \leq 10^9)$ of them showing the length of the $i$-th stick.

Then follow $Q$ lines. $i$-th of them contains two integers $l_i, r_i(1 \leq l_i \leq r_i \leq N)$, meaning that you can only use sticks between $l_i$-th to $r_i$-th.

It is guaranteed that the sum of $N$s and the sum of $Q$s in all test cases are both no larger than $4 \times 10^5$.

Output

For each test case, output $Q$ lines, each containing an integer denoting the maximum circumference.

5 3
2 5 6 5 2
1 3
2 4
2 5

13
16
16