Bob's teachers have conspired to give Bob a major assessment in each of their classes on the same day! Bob has $N$ classes and has estimated how much he will suffer from each assessment. He has recorded these estimates in an array of $N$ positive integers $v_1,v_2,\dots ,v_N$. He defines the suffering of a subarray to be the product of the minimum element in this subarray and the total sum of the subarray. Given $Q$ queries of the form l r, output the greatest suffering of any subarray contained in the subarray from $l$ to $r$ inclusive where the indices are 1-indexed.

Constraints

$1\le v_i\le 1000000$
$1\le l\le r\le N$

Subtask 1 [4%]

$N\le 3000,Q\le 10$

Subtask 2 [15%]

$N\le 5000,Q\le 5000$

Subtask 3 [17%]

$N\le 100000,Q\le 100000$
There are at most $2$ different values of $v_i$

Subtask 4 [24%]

$N\le 100000,Q\le 100000$
There are at most $20$ different values of $v_i$

Subtask 5 [40%]

$N\le 200000,Q\le 200000$
No additional constraints

Input Specification

The first line will contain two space-separated integers, $N$ and $Q$.
The next line will contain $N$ space-separated integers, $v_1,\dots ,v_N$.
The next $Q$ lines will each contain a query of the form l r.

Output Specification

For each of the $Q$ queries, output a single integer, the largest suffering of a subarray contained in the queried subarray.

Sample Input 1

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

Sample Output 1

25
25
26
30

Explanation for Sample 1

For the first query, the subarray $[2,2]$ gives a suffering of $5\cdot 5=25$.
For the second query, the subarray $[2,2]$ gives a suffering of $5\cdot 5=25$.
For the third query, the subarray $[1,4]$ gives a suffering of $2\cdot (3+5+2+3)=26$.
For the fourth query, the subarray $[2,5]$ gives a suffering of $2\cdot (5+2+3+5)=30$.

Sample Input 2

5 10
1 2 2 3 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 2

4
8
14
25
8
14
25
10
25
25

Sample Input 3

10 12
8 2 5 4 1 5 9 8 7 3
1 10
2 4
3 7
7 9
4 6
2 3
7 7
5 10
3 3
1 4
6 8
2 8

Sample Output 3

168
36
81
168
25
25
81
168
25
64
136
136