Республиканская олимпиада по информатике 2011 года за 11 класс | Казахстанские олимпиады

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

Ограничение по времени Ограничение по памяти
2 секунды 256 мегабайта

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

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

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

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

Выходной файл должен содержать ровно MM строк. ii-я строка должна содержать количество различных чисел на интервале массива A,A, заданном на (i+3)(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