Problem A
An Easy Array Problem

This is an array problem.

Given $N$ numbers, $A_1, \dots A_ N$, answer $Q$ queries as follows:

Given $L, R$ where $R - L + 1 \geq 4$, among all possible $L < X < Y < R$, maximise $A_ L \times A_ X \times A_ Y \times A_ R$. Output on a single line this maximised value.

Constraints

$1 \leq N, Q \leq 5 \times 10^5$
$-10^4 \leq A_ i \leq 10^4$
$1 \leq L_ i < L_ i+3 \leq R_ i \leq N$

Input

The first line contains two space-separated integers, $N$, the number of numbers, and $Q$, the number of queries
The second line contains $N$ space-separated integers, $A_1, A_2, \dots , A_ N$
$Q$ lines follow, the $i^{th}$ line contains 2 space-separated integers, $L_ i, R_ i$, which are the $L, R$ values for the $i^{th}$ query

Output

Output $Q$ lines, each containing a single integer which is the answer for the $i^{th}$ query.

7 3
-1 2 1 4 -2 -3 2 
1 7
2 7
1 6

24
24
24

10 10
564 7167 -4069 -3244 579 199 -9838 2913 9796 4734 
2 6
1 6
2 7
1 7
4 10
1 9
5 10
1 7
4 9
5 9

18826041697788
1481496793296
166115621837646
161812108318536
1480010149948608
221168049823968
78216085767528
161812108318536
910703330545056
3287917420308