시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 13 7 7 77.778%

문제

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: AL, AL+1, ..., AR로 이루어진 수열에서 부분 수열의 합으로 나타낼 수 없는 가장 작은 음이 아닌 정수를 출력한다.

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

2
4
8
8
8

출처