Page not loading? Try clicking here.
Placeholder

#8492

서로 다른 숫자 세기 2 1s 1024MB

Problems

A 수열의 특정 구간에서 서로 다른 숫자의 개수를 세라.


Input

A 수열의 길이 N이 주어진다. (1 \le N \le 100\,000)

N개의 수열 값인 A_1, ..., A_N가 주어진다. 수열 값은 N이하의 자연수이다.

질의의 수 Q가 주어진다. (1 \le Q \le 100\,000)

Q개의 질의가 줄 단위로 주어진다.

각 질의는 구간으로 2개의 정수 i,j로 주어진다. A_i 부터 A_j까지 서로 다른 숫자의 개수를 출력한다.

( 1\le i \le j \le N)


Output

Q개의 질의에 대해 각 줄마다 구간의 서로 다른 숫자의 개수를 출력한다.


Example 

6
1 2 3 2 3 1
3
1 6
2 5
3 3
3
2
1


Source

eva

You must sign in to write code.