F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4299. -- Codechef FRBSUM

4299: Codechef FRBSUM

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 784  Solved: 504
[Submit][Status][Discuss]

Description

数集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是多少。

Input

输入数据的第一行包含一个整数N,表示序列的长度。
接下来一行包含N个数,表示给定的序列A(从1标号)。
接下来一行包含一个整数M,表示询问的组数。
接下来M行,每行一对整数,表示一组询问。

Output

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

Sample Input

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

Sample Output

2
4
8
8
8

HINT

对于100%的数据,1≤N,M≤100000,1≤A_i≤10^9,1≤A_1+A_2+…+A_N≤10^9。


Source

By yts1999

[Submit][Status][Discuss]

HOME Back