CF455E.Function

Serega and Fedor play with functions. One day they came across a very interesting function. It looks like that:

• f(1, j) = a[j], 1 ≤ j ≤ n.
• f(i, j) = min(f(i - 1, j), f(i - 1, j - 1)) + a[j], 2 ≤ i ≤ n, i ≤ j ≤ n.

Here a is an integer array of length n.

Serega and Fedya want to know what values this function takes at some points. But they don't want to calculate the values manually. So they ask you to help them.

谢尔加和费多尔在研究函数。一天，他们遇到了一个非常有趣的函数，其定义如下：

• $ f(1, j) = a[j] $，其中 $ 1 \leq j \leq n $；
• $ f(i, j) = \min(f(i-1, j),, f(i-1, j-1)) + a[j] $，其中 $ 2 \leq i \leq n $，$ i \leq j \leq n $。

其中 $ a $ 是一个长度为 $ n $ 的整数数组。

谢尔加和费多尔想知道该函数在某些点处的取值。但他们不想手动计算这些值，因此请你帮助他们。

The first line contains integer n (1 ≤ n ≤ 105) — the length of array a. The next line contains n integers: a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 104).

The next line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains two integers: x__i, y__i (1 ≤ x__i ≤ y__i ≤ n). Each line means that Fedor and Serega want to know the value of f(x__i, y__i).

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 数组 $a$ 的长度。
下一行包含 $n$ 个整数：$a[1],\ a[2],\ \dots,\ a[n]$（$0 \leq a[i] \leq 10^4$）。

接下来一行包含一个整数 $m$（$1 \leq m \leq 10^5$）—— 查询的数量。
接下来的 $m$ 行，每行包含两个整数：$x_i,\ y_i$（$1 \leq x_i \leq y_i \leq n$）。
每行表示 Fedor 和 Serega 想要求出 $f(x_i,\ y_i)$ 的值。

Print m lines — the answers to the guys' queries.

输出 m 行——即各位查询的答案。