Problem Description

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.

Input Format

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 Format

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

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

90
90
90
2
90
56
72
90

Hint

Translated by ChatGPT 5