一个可重复数字集合 $S$ 的神秘数定义为最小的不能被 $S$ 的子集的和表示的正整数。

例如 $S=\{1,1,1,4,13\}$，

1 = 1
2 = 1+1
3 = 1+1+1
4 = 4
5 = 4+1
6 = 4+1+1
7 = 4+1+1+1

$8$ 无法表示为集合 $S$ 的子集的和，故集合 $S$ 的神秘数为 $8$。

现给定 $n$ 个正整数 $a_1..a_n$，$m$ 个询问，每次询问给定一个区间 $[l,r]$，求由 $a_l,a_{l+1},…,a_r$ 所构成的可重复数字集合的神秘数。

输入格式

第一行一个整数 $n$，表示数字个数。

第二行 $n$ 个整数，从 $1$ 编号。

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

以下 $m$ 行，每行一对整数 $[l,r]$，表示一个询问。

输出格式

对于每个询问，输出一行对应的答案。

数据范围

$1 \le n,m \le 10^5$,
$\sum a_i \le 10^9$

输入样例：

5
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5

输出样例：

2
4
8
8
8