Description

一个可重复数字集合 $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$，表示询问个数。

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

提示说明

$1\le n,m\le10^5,\sum a\le10^9$