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