정수 \(N\)개로 이루어진 수열이 주어진다.

구간을 나타내는 질의가 \(Q\)개 주어질 때, 각 구간에 있는 서로 다른 정수의 개수를 구하시오.

입력

첫째 줄에 수열의 길이 \(N\)과 질의의 수 \(Q\)가 공백으로 구분되어 주어진다.

둘째 줄에 수열의 원소 \(a_1, a_2, \ldots, a_N\)이 공백으로 구분되어 주어진다.

다음 \(Q\)개의 줄에 두 정수 \(L\)과 \(R\)이 공백으로 구분되어 주어진다. 이는 수열의 \(L\)번째 원소부터 \(R\)번째 원소까지의 구간을 의미한다.

출력

각 질의마다 해당 구간에 있는 서로 다른 정수의 개수를 한 줄에 하나씩 출력한다.

제한 사항

• \(1 \le N, Q \le 1,000\)
• \(-1,000,000,000 \le a_i \le 1,000,000,000\)
• \(1 \le L \le R \le N\)

예제 입력 1

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

예제 출력 1

3
3
1
2