길이 \(N\)의 수열 \(A\)가 주어진다.
Q개의 질의가 주어진다.

각 질의는 \(l\) \(r\) 형태이며, 수열의 구간 \(A_l, A_{l+1}, \dots, A_r\)에 등장하는 서로 다른 수의 개수를 출력해야 한다.

\(1 ≤ N ≤ 200\,000\)
\(1 ≤ Q ≤ 200\,000\)
\(1 ≤ A_i ≤ 1\,000\,000\,000\)
\(1 ≤ l ≤ r ≤ N\)

첫째 줄에 수열의 길이 \(N\)과 질의의 개수 \(Q\)가 주어진다.

둘째 줄에 수열의 원소 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.

셋째 줄부터 \(Q\)개의 줄에 걸쳐 각 질의 \(l\) \(r\)이 주어진다.

각 질의마다 구간 \(A_l, A_{l+1}, \dots, A_r\)에 등장하는 서로 다른 수의 개수를 한 줄에 하나씩 출력한다.

anthony0506 작성

출처 anthony0506