P9275 [AGM 2023 Qualifier] DrahSort

Given a sequence $A$ of length $N$, you will receive $Q$ queries. - For each query $[l, r]\ (l \leq r)$, output the maximum value of the product of two adjacent numbers that are swapped if you perform bubble sort on this interval.

The first line contains an integer $N(1 \leq N \leq 2 \times 10^5)$, representing 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)$, which are the elements of the array. The third line contains an integer $Q(1 \leq Q \leq 2 \times 10^5)$, representing the number of operations. Each of the next $Q$ lines contains a query as described in the statement.

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

Translated by ChatGPT 5