페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3568

배열과 쿼리 3 5s 1024MB

문제

​길이가 n인 배열 A_1, A_2, ..., A_n이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

l r: A_l, A_{l+1}, …, A_r 중 서로 다른 수의 개수를 출력한다.​ 


입력

첫째 줄에 배열의 크기 n과 쿼리의 개수 q (1 ≤ n, q ≤ 1,000,000)가 주어진다.

둘째 줄에는 A_1, A_2, ..., A_n이 주어진다. (1 ≤ A_i ≤ n)

다음 q개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ l ≤ r ≤ n)


출력

쿼리가 주어질 때 마다 정답을 한 줄에 하나씩 출력한다.​


예제 

10 10

1 3 2 1 3 1 3 2 1 3

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

로그인해야 코드를 작성할 수 있어요.