函数

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定长度为 $n$ 的非负整数数组 $a$，定义函数 $f$：

• $f(1,j)=a_j$，其中 $1\le j\le n$；
• $f(i,j)=\min(f(i-1,j),f(i-1,j-1))+a_j$，其中 $2\le i\le n$ 且 $i\le j\le n$。

你需要回答若干询问。每个询问给出 $x,y$，求 $f(x,y)$。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第三行包含一个整数 $m$，表示询问数量。

接下来 $m$ 行，每行包含两个整数 $x,y$。

输出格式

对每个询问输出一行一个整数，表示 $f(x,y)$。

样例输入 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

数据范围

$1\le n,m\le10^5$，$0\le a_i\le10^4$，$1\le x\le y\le n$。