Республиканская олимпиада по информатике, 2011 год, 10-11 классы

Задача D. Уникальные числа

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайта

Вам дан массив целых чисел $A$ длины $N$ и набор из $M$ интервалов $[l, r]$ этого массива. Для каждого из интервалов вам необходимо найти количество различных чисел среди $A[l],$ $A[l + 1],$ $\ldots,$ $A[r].$

Формат входного файла

Первая строка входного файла содержит два целых числа $N$ и $M$ $(1 \le N \le 10^5,$ $1 \le M \le 10^5).$ В следующей строке находится массив $A$: $N$ целых чисел $A[i]$ $(1 \le A[i] \le 10^9).$ В каждой из следующих $M$ строк находятся по два числа $l[i]$ и $r[i]$ $(1 \le l[i] \le r[i] \le N),$ задающих концы соответствующего интервала.

Формат выходного файла

Выходной файл должен содержать ровно $M$ строк. $i$-я строка должна содержать количество различных чисел на интервале массива $A,$ заданном на $(i + 3)$-й строке входного файла.

Примеры:

Вход

6 6
1000 2 3 1 1000 1000
2 3
1 2
4 6
3 6
3 5
1 3

Ответ

2
2
2
3
3
3