Dinosaur Bones Digging

Paleontologists are looking for dinosaur bones! They have already found a long line of $n$ square sectors, numbered from 1 to $n$. Each square has a side of 1 meter. Preliminary measurements showed that in sector $i$, the depth of soil potentially containing dinosaur bones is $a_i$ meters. Below that depth lies solid bedrock. All the numbers $a_i$ are distinct integers.

Scientists have prepared $q$ research plans. Each plan builds a research station on the subsegment of sectors from $\ell_j$ to $r_j$. After picking the subsegment, they pick one of its sectors $m$ ($\ell_j \le m \le r_j$) as the main sector.

A special device is buried in the main sector at a depth of $a_m$ meters. The device analyzes the top $a_m$ meters of every sector under the station whose depth is strictly greater than $a_m$. In total, $a_m \cdot k$ cubic meters of soil are analyzed, where $k$ is the number of sectors under the station (between $\ell_j$ and $r_j$, inclusive) that are deeper than the main sector.

The paleontologists want to analyze as much soil as possible. Find the maximum volume of soil that can be analyzed when one plan is chosen and its main sector is then chosen optimally.

The first line contains a single integer $n$, the number of sectors ($1 \le n \le 10^6$).

The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$, the depths of the sectors ($1 \le a_i \le 10^9$).

The next line contains a single integer $q$, the number of plans ($1 \le q \le 10^6$).

Each of the next $q$ lines contains two integers $\ell_j$ and $r_j$, the endpoints of the subsegment for the $j$-th plan ($1 \le \ell_j \le r_j \le n$).

Print a single integer on one line: the maximum volume of analyzed soil in cubic meters.

In the example, the scientists should pick the first plan and the first sector as its main sector. Then $3 \cdot 3 = 9$ cubic meters of soil are analyzed, since $5$, $7$, and $4$ are deeper than $3$.