Study nature: A talent who explores nature and discovers problems in the world.

The sentence above is a part of the motto revealed in KSA Vision 2040.

However, since the author of this problem has already graduated from KSA, they decided to copy someone else's problem. This problem is a copy of Largest Rectangle in a Histogram and Queries, with only a few letters changed.

A histogram is a polygon composed of several rectangles aligned at the bottom. Each rectangle has a constant width of 1, but their heights may vary. For example, the following figure shows a histogram consisting of rectangles with heights 3, 5, 8, 8, 4, 7.

Let's perform $Q$ queries of the following type on the histogram.

• $l$ $r$: Print the area of the largest rectangle when only the rectangles from the $l$-th to the $r$-th are present.

Input

The first line contains the number of rectangles $N$.

The second line contains $N$ space-separated integers $H_1, H_2, \cdots, H_N$ representing the heights of the rectangles in the histogram from left to right.

The third line contains the number of queries $Q$.

The following $Q$ lines contain the information of the queries, where each line contains two space-separated integers $l$ and $r$.

Output

Print the answer to each query over $Q$ lines.

Constraints

• $1 \le N, Q \le 10^5$
• $1 \le H_i \le 10^9$
• $1 \le l \le r \le N$

Scoring

Examples

Input 1

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

Output 1

20
10
16
16
12