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 1\,000\,000~
~1 \le l \le r \le N~

Subtask 1 [4%]

~N \le 3\,000, Q \le 10~

Subtask 2 [15%]

~N \le 5\,000, Q \le 5\,000~

Subtask 3 [17%]

~N \le 100\,000, Q \le 100\,000~
There are at most ~2~ different values of ~v_i~

Subtask 4 [24%]

~N \le 100\,000, Q \le 100\,000~
There are at most ~20~ different values of ~v_i~

Subtask 5 [40%]

~N \le 200\,000, Q \le 200\,000~
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