数集S的ForbiddenSum定义为无法用S的某个子集（可以为空）的和表示的最小的非负整数。

给定一个序列A，你的任务是回答该数列的一些子区间所形成的数集的ForbiddenSum是多少。

输入数据的第一行包含一个整数N，表示序列的长度。

接下来一行包含N个数，表示给定的序列A（从1标号）。

接下来一行包含一个整数M，表示询问的组数。

接下来M行，每行一对整数，表示一组询问。

对于每组询问，输出一行表示对应的答案。

对于100%的数据，1≤NM≤1000001≤A_i≤10^9，1≤A_1+A_2+…+A_N≤10^9。