문제

길이가 N인 정수 수열 A_1, A_2, ..., A_N이 주어진다. 이때 다음 형태의 쿼리 M개가 주어질 때, 각 쿼리의 답을 구하는 프로그램을 작성하시오.

• i j: 구간 A_i, A_{i+1}, ..., A_j 중에서 중복을 제외하고 서로 다른 정수가 몇 종류 존재하는지 출력한다.

(단, 항상 입력되는 쿼리는 1 ≤ i ≤ j ≤ N을 만족한다.)

입력

첫째 줄에 수열의 크기 N과 쿼리의 개수 M이 공백을 사이에 두고 주어진다. 둘째 줄에는 수열을 이루는 N개의 정수가 공백을 사이에 두고 주어진다. 셋째 줄부터 M개의 줄에는 각 쿼리를 나타내는 두 정수 i, j가 주어진다.

(단, 1 ≤ N, M ≤ 100,000, 수열의 원소는 1 이상 1,000,000,000 이하의 자연수이다.)

출력

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

예제 입력 1

5 3
1 2 1 3 2
1 5
2 4
3 5

예제 출력 1

3
3
3

예제 설명 1

• 첫 번째 쿼리 [1, 5]: 구간 [1, 2, 1, 3, 2]에서 서로 다른 숫자는 1, 2, 3으로 총 3개이다.
• 두 번째 쿼리 [2, 4]: 구간 [2, 1, 3]에서 서로 다른 숫자는 2, 1, 3으로 총 3개이다.
• 세 번째 쿼리 [3, 5]: 구간 [1, 3, 2]에서 서로 다른 숫자는 1, 3, 2로 총 3개이다.