공룡 뼈 발굴

고생물학자들이 공룡 뼈를 찾고 있다. 이들은 1부터 $n$까지 번호가 붙은 $n$개의 정사각형 구역이 늘어선 긴 줄을 이미 발견했다. 각 정사각형의 한 변은 1미터이다. 예비 측정 결과, 구역 $i$에서 공룡 뼈가 묻혀 있을 가능성이 있는 흙의 깊이는 $a_i$미터이다. 그 아래는 단단한 암반이다. 모든 $a_i$는 서로 다른 정수이다.

연구팀은 $q$개의 연구 계획을 세웠다. 각 계획은 구역 $\ell_j$부터 $r_j$까지의 부분 구간에 연구소를 짓는다. 구간을 고른 뒤에는 그 안의 구역 $m$($\ell_j \le m \le r_j$) 하나를 주 구역으로 고른다.

주 구역의 깊이 $a_m$미터 지점에 특수 장치를 묻는다. 이 장치는 연구소 아래 구역 중 깊이가 $a_m$보다 깊은 구역마다 위쪽 $a_m$미터의 흙을 분석한다. 분석되는 흙의 총량은 $a_m \cdot k$세제곱미터이다. 여기서 $k$는 연구소 아래 구역(양 끝 $\ell_j$와 $r_j$를 포함) 중 주 구역보다 깊은 구역의 수이다.

고생물학자들은 흙을 최대한 많이 분석하려 한다. 계획 하나를 고르고 그 주 구역을 최적으로 골랐을 때, 분석할 수 있는 흙의 최대 부피를 구하라.

첫 줄에 구역의 수 $n$이 주어진다 ($1 \le n \le 10^6$).

둘째 줄에는 구역의 깊이를 나타내는 서로 다른 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^9$).

다음 줄에는 계획의 수 $q$가 주어진다 ($1 \le q \le 10^6$).

이어지는 $q$개의 줄 중 $j$번째 줄에는 $j$번째 계획의 부분 구간 양 끝 $\ell_j$와 $r_j$가 주어진다 ($1 \le \ell_j \le r_j \le n$).

분석할 수 있는 흙의 최대 부피를 세제곱미터 단위의 정수로 한 줄에 출력한다.

예제에서 연구팀은 첫 번째 계획을 고르고, 주 구역으로 첫 번째 구역을 고른다. $5$, $7$, $4$가 $3$보다 깊으므로 $3 \cdot 3 = 9$세제곱미터의 흙이 분석된다.