P9285 [AGM 2023 Qualifier] YsaeSort

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.

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 $Q$ lines. For each query, output the answer.

Translated by ChatGPT 5