Maximum Swap Product in Bubble Sort

You are given a sequence \(A\) of length \(N\). You need to answer \(Q\) queries. In each query, you are given two integers \(l\) and \(r\) (with \(l \le r\)), which represent a subarray of \(A\): \(A[l], A[l+1], \ldots, A[r]\). Consider performing Bubble Sort on this subarray. Every time two adjacent elements are swapped because the left element is greater than the right element, record the product of these two numbers. Your task is to output the maximum product among all such swaps that occur during the Bubble Sort process. If no swap occurs (i.e. the subarray is already sorted in non-decreasing order), output \(-1\).

Note: It can be shown that during Bubble Sort, every inversion (a pair \(A[i]\) and \(A[j]\) with \(i A[j]\)) will eventually be swapped when they become adjacent. Therefore, the answer is equivalent to computing the maximum \(A[i] \times A[j]\) over all inversion pairs \((i, j)\) in the subarray \(A[l \ldots r]\).

inputFormat

The first line contains two integers \(N\) and \(Q\) \((1 \leq N, Q \leq 2000)\), representing the length of the sequence and the number of queries, respectively.

The second line contains \(N\) integers \(A_1, A_2, \ldots, A_N\) \((1 \leq A_i \leq 10^9)\) representing the sequence.

Each of the next \(Q\) lines contains two integers \(l\) and \(r\) \((1 \leq l \leq r \leq N)\) representing a query.

outputFormat

For each query, output a single line containing the maximum product of two adjacent numbers swapped during the Bubble Sort process on the subarray \(A[l \ldots r]\). If no swap occurs, output \(-1\).

sample

3 2
3 1 2
1 3
2 3

6
-1