B. DrahSort
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

This problem is similar to YsaeSort. Please read the problem statement carefully to understand the differences

You are given an array of $$$N$$$ non-negative integers and a list of $$$Q$$$ operations that need to be performed on it. Each operation has the following meaning:

  • $$$l$$$ $$$r$$$ $$$(1 \leq l \leq r \leq N)$$$ - find the minimum required cost to sort the contiguous subsequence $$$[l, r]$$$ of the array

The cost required to sort a substring, $$$[l, r]$$$ ($$$1 \leq l \leq r \leq N$$$), is defined as follows. You are only allowed to swap consecutive elements from the substring (any pair of indices $$$(i, i + 1)$$$ such that $$$l \leq i \leq r - 1$$$). The cost of swapping two consecutive elements is the product of the elements being swapped. The cost of sorting the entire substring is defined as the maximum cost among each individual swap.

Please note that the operations won't alter the structure of the array.

Input

The first line of input will contain one integer $$$N$$$ ($$$1\leq N \leq 2 \cdot 10^5$$$), representing the number of elements of the array.

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

The third line of input will contain one integer $$$Q$$$ ($$$1\leq Q \leq 2 \cdot 10^5$$$), representing the number of operations.

Each of the following $$$Q$$$ lines will contain one operation as described in the problem statement.

Output

For every query output the required cost to sort the substring.

Example
Input
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
Output
90
90
90
2
90
56
72
90