시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 1024 MB 23 13 12 54.545%

문제

총 N개의 정수로 이루어진 배열 A가 주어진다. 이 때, 다음 쿼리를 총 Q번 반복 수행하는 프로그램을 작성하시오. 배열은 1번부터 시작한다.

  • l r: l번째 수부터 r번째 수 중에서 서로 다른 수의 개수를 세고 출력한다.

입력

첫째 줄에 배열의 크기 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 배열에 포함된 수가 1번째 수부터 주어진다. 수는 공백으로 구분되어져 있다. 배열에 포함된 수는 1,000,000,000보다 작거나 같은 자연수이다.

셋째 줄에는 쿼리의 개수 Q(1 ≤ Q ≤ 1,000,000)가 주어진다. 넷째 줄부터 Q개의 줄에는 쿼리를 나타내는 두 정수 xi, ri가 주어진다. 이 때, li = xi + Qi-1로 구한다. (1 ≤ li ≤ ri ≤ N, -(N-1) ≤ xi ≤ (N-1)) Qi는 i번 쿼리의 정답이고, 첫 쿼리의 번호는 1번이다. 마지막으로, Q0 = 0이다.

출력

첫째 줄부터 Q개의 줄에 쿼리의 답을 한 줄에 하나씩 출력한다.

예제 입력

10
1 3 2 1 3 1 3 2 1 3 
10
8 9
2 7
4 8
1 6
1 7
-1 10
0 8
-2 10
1 7
-1 7

예제 출력

2
2
3
2
3
3
3
3
2
3

힌트

출처