Function and Queries

You are given an array $a = (a_1, a_2, \dots, a_n)$ of length $n$. The function $f$ is defined as follows.

$f(1,\, j) = a_j \qquad (1 \le j \le n)$

$f(i,\, j) = \min(f(i-1,\, j),\ f(i-1,\, j-1)) + a_j \qquad (2 \le i \le n,\ i \le j \le n)$

You are also given $m$ queries. Each query consists of two integers $x_i$ and $y_i$, and asks for the value of $f(x_i, y_i)$. Write a program that answers every query.

The first line contains the size $n$ of the array $a$ ($1 \le n \le 10^5$).

The second line contains $a_1, a_2, \dots, a_n$ separated by spaces. ($0 \le a_j \le 10^4$)

The third line contains the number of queries $m$ ($1 \le m \le 10^5$). Each of the next $m$ lines contains one query as $x_i$ and $y_i$. ($1 \le x_i \le y_i \le n$)

Print the value of $f(x_i, y_i)$ for each query, one per line, in the order the queries are given.