BZPRO
#4299. Codechef FRBSUM
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
数集S的ForbiddenSum定义为无法用S的某个子集（可以为空）的和表示的最小的非负整数。
例如，S={1,1,3,7}，则它的子集和中包含0(S’=∅)，1(S’={1})，2(S’={1,1})，3(S’={3})，4(S’={1,3})，5(S' = {1, 1, 3})，但是它无法得到6。因此S的ForbiddenSum为6。
给定一个序列A，你的任务是回答该数列的一些子区间所形成的数集的ForbiddenSum是多少。
输入格式
输入数据的第一行包含一个整数N，表示序列的长度。
接下来一行包含N个数，表示给定的序列A（从1标号）。
接下来一行包含一个整数M，表示询问的组数。
接下来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≤N,M≤100000,1≤A_i≤10^9，1≤A_1+A_2+…+A_N≤10^9。
BZPRO