题目描述

一个可重复数字集合 $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$，$m$ 次询问，每次询问包含两个参数 $l,r$，你需要求出由 $a_l,a_{l+1},\cdots,a_r$ 所组成的可重集合的神秘数。

输入格式

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

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

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

输出格式

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

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

2
4
8
8
8

提示

对于 $100\%$ 的数据点，$1\le n,m\le {10}^5$，$\sum a\le {10}^9$。