만들 수 없는 부분 수열의 합

길이가 $N$인 수열 $A$가 주어진다. 부분 수열은 $A$에서 원소를 일부 지워 만든 수열이고, 원소를 모두 지우는 것도 가능하므로 빈 수열도 부분 수열이다. 부분 수열의 합은 그 부분 수열에 남은 정수를 모두 더한 값이며, 빈 부분 수열의 합은 0이다.

예를 들어 $A$가 [1, 1, 3, 7]이면 부분 수열 [], [1], [1, 1], [3], [1, 3], [1, 1, 3]의 합은 차례로 0, 1, 2, 3, 4, 5이다. 6은 어떤 부분 수열의 합으로도 만들 수 없으므로, $A$의 부분 수열의 합으로 나타낼 수 없는 가장 작은 음이 아닌 정수는 6이다.

쿼리 $M$개가 주어진다. 각 쿼리는 두 정수 $L$, $R$로 이루어지고, 수열 $A_L, A_{L+1}, \dots, A_R$의 부분 수열의 합으로 나타낼 수 없는 가장 작은 음이 아닌 정수를 묻는다. 모든 쿼리의 답을 구하는 프로그램을 작성하시오.

첫째 줄에 수열의 크기 $N$ ($1 \le N \le 100000$)이 주어진다. 둘째 줄에 수열 $A_1, A_2, \dots, A_N$이 주어진다. 각 수는 $10^9$ 이하의 자연수이고, 수열에 있는 수를 모두 더한 값도 $10^9$ 이하이다.

셋째 줄에 쿼리의 개수 $M$ ($1 \le M \le 100000$)이 주어진다. 넷째 줄부터 $M$개의 줄에 쿼리가 한 줄에 하나씩 $L_i$ $R_i$ ($1 \le L_i \le R_i \le N$) 형태로 주어진다.

각 쿼리의 답을 입력 순서대로 한 줄에 하나씩 출력한다.