ForbiddenSum

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Mike likes to invent new functions. The latest one he has invented is called ForbiddenSum. Let's consider how it can be calculated:
You are given a set S of positive integers. The integers are not necessary distinct. ForbiddenSum of S equals to the minimal nonnegative integer, that can't be returned by the algorithm described below:
 Choose a random subset S' of S(it can be empty as well);
 Calculate the sum of all the numbers of S' and assign it to the variable T;
 Return the value of the variable T.
I.e. if S = {1, 1, 3, 7}, the algorithm can return 0(S' = {}), 1(S' = {1}), 2(S' = {1, 1}), 3(S' = {3}), 4(S' = {1, 3}), 5(S' = {1, 1, 3}), but it can't return 6. So, ForbiddenSum of S equals to 6.
Inventing of new function is not the only Mike's hobby. Also, he likes to collect rare and unusual arrays. He is going to share with you one of them.
Formally, Mike gives you one array A, consisting of N positive integers. After that, he asks you M questions, two integers L_{i} and R_{i} describe i'th question: What does ForbiddenSum of S={A_{Li}, A_{Li+1}, ..., A_{Ri1}, A_{Ri}} equal to?
Input
The first line contains the only integer N. The second line contains N integers  the array A. A is 1indexed.
The third line contains the only integer M. The following M lines contain two integer numbers 1 ≤ L_{i} ≤ R_{i} ≤ N each.
Output
Output should consists of M lines. The i'th line should contains the answer to the i'th question.
Constraints
1 ≤ N, M ≤ 100,000
1 ≤ A_{i} ≤ 10^{9}
1 ≤ A_{1} + A_{2} + ... + A_{N} ≤ 10^{9}
Example
Input: 5 1 2 4 9 10 5 1 1 1 2 1 3 1 4 1 5 Output: 2 4 8 8 8
Explanation
In the example test there are M=5 questions. We won't describe all of them, only two ones.
The first question
In the first test case S equals to {1}. The answer is 2, because we can recieve 1 in case the algorithm chooses S' = {1}. But there are no chances to receive 2.
The second question
In the first test case S equals to {1, 2}. The answer is 4, because we can recieve 1 in case the algorithm chooses S' = {1}, 2 in case the algorithm chooses S' = {2} and 3 in case the algorithm chooses S' = {1, 2}. But there are no chances to receive 4.
Author:  kostya_by 
Tester:  white_king 
Editorial  http://discuss.codechef.com/problems/FRBSUM 
Tags  binarysearch, jan14, kostya_by, medium, persistence, segmenttree 
Date Added:  18102013 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 