구간에 있는 서로 다른 수의 개수

시간 제한5초메모리 제한1024 MB

요약
배열이 주어질 때 여러 구간 질의에 대해 그 구간에 등장하는 서로 다른 값의 개수를 센다.
난이도

보통10점 중 7점

유형
배열, 정렬, 누적 합, 비트 연산
정답자
아직 제출이 없습니다

문제

정수 NN개로 이루어진 배열 AA가 주어진다. 배열의 첫 원소는 1번이다.

아래 쿼리를 QQ번 처리하는 프로그램을 작성하시오.

  • l r: ll번째 수부터 rr번째 수까지에서 서로 다른 수가 몇 개인지 세어 출력한다.

입력

첫째 줄에 배열의 크기 NN (1≤N≤1061 \le N \le 10^6)이 주어진다.

둘째 줄에 배열의 원소 A1,A2,…,ANA_1, A_2, \dots, A_N이 1번부터 차례대로 공백으로 구분되어 주어진다. 각 원소는 10910^9 이하의 자연수이다.

셋째 줄에 쿼리의 개수 QQ (1≤Q≤1061 \le Q \le 10^6)가 주어진다.

넷째 줄부터 QQ개의 줄에 쿼리가 한 줄에 하나씩 lil_i rir_i 형태로 주어진다 (1≤li≤ri≤N1 \le l_i \le r_i \le N).

출력

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

예제5

  1. 예제 1

    입력
    10
1 3 2 1 3 1 3 2 1 3
10
8 9
4 7
6 8
4 6
3 7
2 10
3 8
1 10
4 7
1 7
    예상 출력
    2
2
3
2
3
3
3
3
2
3

  2. 예제 2

    입력
    1
1000000000
1
1 1
    예상 출력
    1

  3. 예제 3

    입력
    8
7 7 7 7 7 7 7 7
5
1 8
1 1
3 5
8 8
2 7
    예상 출력
    1
1
1
1
1

  4. 예제 4

    입력
    10
10 20 30 40 50 60 70 80 90 100
6
1 10
1 1
5 9
10 10
2 3
4 8
    예상 출력
    10
1
5
1
2
5

  5. 예제 5

    입력
    8
1 1000000000 1 1000000000 999999999 1 999999999 2
8
1 8
1 4
5 8
2 2
3 7
4 5
1 2
7 8
    예상 출력
    4
2
3
1
3
2
2
2