시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 38 | 9 | 8 | 80.000% |
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)
각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.
5 1 2 4 9 10 5 1 1 1 2 1 3 1 4 1 5
2 4 8 8 8