← 返回题目列表

Codeforces · 455/E

E. 功能

中文机器翻译题面 查看原题

Serega 和 Fedor 玩弄函数。有一天他们发现了一个非常有趣的函数。看起来像这样:

- 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。

这里 a 是长度为 n 的整数数组。

Serega 和 Fedya 想知道这个函数在某些时候取什么值。但他们不想手动计算这些值。所以他们请求你帮助他们。

输入

第一行包含整数 n (1 ≤ n ≤ 105) — 数组 a 的长度。下一行包含 n 个整数:a[1]、a[2]、...、a[n] (0 ≤ a[i] ≤ 104)。

下一行包含整数 m (1 ≤ m ≤ 105) — 查询数。接下来的 m 行中的每一行都包含两个整数:xi, yi (1 ≤ xi ≤ yi ≤ n)。每行都表示 Fedor 和 Serega 想知道 f(xi, yi) 的值。

输出

打印 m 行 — 回答这些人的问题。

示例

输入 #1

6
2 2 3 4 3 4
4
4 5
3 4
3 4
2 3

输出 #1

12
9
9
5

输入 #2

7
1 3 2 3 4 0 2
4
4 5
2 3
1 4
4 6

输出 #2

11
4
3
0