Problem Description

Given a sequence $A$ of length $N$, you will perform $Q$ operations:

• $1\ l\ r\ (1 \leq l \leq r \leq N)$ means sorting the interval $[l, r]$.

• $2\ l\ r\ (1 \leq l \leq r \leq N)$ is a query: if you perform bubble sort on this interval, what is the maximum product of the two adjacent numbers that get swapped.

It is guaranteed that the intervals sorted by operation $1$ are pairwise disjoint or one contains another.

Input Format

The first line contains an integer $N\ (1 \leq N \leq 5 \times 10^4)$, the number of elements in the array.

The second line contains $N$ integers $(0 \leq A[i] \leq 10^9,\ 1 \leq i \leq N)$, the elements of the array.

The third line contains an integer $Q\ (1 \leq Q \leq 5 \times 10^4)$, the number of operations.

Each of the next $Q$ lines contains one query described above.

Output Format

Output $Q$ lines. For each query, output the answer.

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

0
80
80
2
80
0
70
0

Hint

Translated by ChatGPT 5