Smallest unreachable subsequence sum

You are given a sequence $A$ of length $N$. A subsequence is what is left after deleting some elements of $A$, and deleting every element is allowed, so the empty sequence is a subsequence too. The sum of a subsequence is the sum of the integers it keeps, and the sum of the empty subsequence is 0.

For example, if $A$ is [1, 1, 3, 7], the subsequences [], [1], [1, 1], [3], [1, 3], [1, 1, 3] have sums 0, 1, 2, 3, 4, 5 in that order. No subsequence sums to 6, so the smallest non-negative integer that is not a subsequence sum of $A$ is 6.

Then $M$ queries are given. Each query consists of two integers $L$ and $R$ and asks for the smallest non-negative integer that is not the sum of any subsequence of $A_L, A_{L+1}, \dots, A_R$. Write a program that answers every query.

The first line contains the length of the sequence $N$ ($1 \le N \le 100000$). The second line contains the sequence $A_1, A_2, \dots, A_N$. Every number is a natural number at most $10^9$, and the sum of all numbers in the sequence is also at most $10^9$.

The third line contains the number of queries $M$ ($1 \le M \le 100000$). Each of the next $M$ lines contains one query in the form $L_i$ $R_i$ ($1 \le L_i \le R_i \le N$).

Print the answer to each query on its own line, in the order the queries are given.