Bubble Sort Swap Maximum Product

You are given a sequence \(A\) of length \(N\) and you need to process \(Q\) operations. There are two types of operations:

• 1 l r: Sort the subarray \(A[l \ldots r]\) in non-decreasing order. It is guaranteed that the sorting intervals from type 1 operations are either non-intersecting or one is contained in the other.
• 2 l r: Consider the subarray \(A[l \ldots r]\). If you perform a bubble sort on this subarray, record the product of the two adjacent elements swapped in every swap operation. Output the maximum such product. If no swap occurs (i.e. the subarray is already sorted), output -1.

Bubble sort works as follows on an array \(B\) of length \(m\):

\[ \begin{array}{l} \textbf{repeat} \quad \text{flag} = \text{false} \\ \quad \textbf{for } i=0 \textbf{ to } m-2 \textbf{ do} \\ \quad\quad \text{if } B[i] > B[i+1] \text{ then} \\ \quad\quad\quad \text{record } B[i] \times B[i+1], \quad \text{swap } B[i] \text{ and } B[i+1] \\ \quad\quad\quad \text{flag } = \text{true} \\ \quad \textbf{end for} \\ \textbf{until flag is false} \\ \end{array} \]

Your task is to process the operations in order and output the answer for each query of type 2.

inputFormat

The first line contains two integers \(N\) and \(Q\), representing the length of the sequence and the number of operations.

The second line contains \(N\) integers \(A_1, A_2, \ldots, A_N\) representing the sequence.

The next \(Q\) lines each describe an operation in one of the following formats:

• 1 l r : Sort the subarray \(A[l \ldots r]\).
• 2 l r : Query the maximum product among adjacent swapped pairs when bubble sorting the subarray \(A[l \ldots r]\). If no swap occurs, output -1.

outputFormat

For each operation of type 2, output one integer representing the answer to the query.

sample

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

20
15
8

</p>