Mo's 알고리즘 (기본)

N개의 정수 수열과 Q개의 쿼리가 있다. 각 쿼리 [L, R]에 대해 A[L]부터 A[R] 중 서로 다른 수의 개수를 구한다. Mo's 알고리즘으로 오프라인 처리한다.

입력

첫째 줄에 N과 Q가 주어진다. (1 ≤ N, Q ≤ 100,000)
둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. (1 ≤ Ai ≤ 1,000,000)
다음 Q개의 줄에 L과 R이 주어진다. (1 ≤ L ≤ R ≤ N)

출력

각 쿼리에 대한 답을 입력 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

2
3
3