14896번 - 만들 수 없는 부분 수열의 합

N개의 수로 이루어진 수열 A가 주어졌을 때, 부분 수열의 합으로 나타낼 수 없는 가장 작은 음이 아닌 정수를 구하려고 한다.

부분 수열이란 수열에서 수를 일부 지워서 만드는 수열이며, 모든 수를 지우는 것도 가능하다. 부분 수열의 합이란 부분 수열에 포함된 모든 정수를 더한 값을 의미한다.

예를 들어, A = [1, 1, 3, 7]인 경우 부분 수열을 일부 써보면, [], [1], [1,1], [3], [1,3], [1,1,3]이 있다. 부분 수열의 합을 구해보면 순서대로 0, 1, 2, 3, 4, 5이다. 이때, 6은 부분 수열의 합으로 만들 수 없기 때문에, A의 부분 수열의 합으로 나타낼 수 없는 가장 작은 음이 아닌 정수가 된다.

M개의 쿼리가 주어졌을 때, 각 쿼리의 답을 구하는 프로그램을 작성하시오. 각 쿼리는 L, R로 이루어져 있으며, 아래와 같은 형식이다.

• L R: A_L, A_L+1, ..., A_R로 이루어진 수열에서 부분 수열의 합으로 나타낼 수 없는 가장 작은 음이 아닌 정수를 출력한다.

첫째 줄에 수열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 수열이 주어진다. 수는 10⁹보다 작거나 같은 자연수이고, 수열에 포함된 수를 모두 더한 값은 10⁹보다 작거나 같다.

셋째 줄에는 쿼리의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 넷째 줄부터 M개의 줄에는 쿼리 L_i, R_i이 주어진다. (1 ≤ L_i ≤ R_i ≤ N)

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.