Олимпиадный тренинг

Задача . B. Маленький Слоник и массив


Задача

Темы: Конструктив Структуры данных *1800

Маленький Слоник любит играть с массивами. У него есть массив a, состоящий из n целых положительных чисел, пронумерованных от 1 до n. Обозначим число с номером i через ai.

Дополнительно у Маленького Слоника есть m запросов к массиву, каждый запрос описывается парой целых чисел lj и rj (1 ≤ lj ≤ rj ≤ n). Для каждого запроса lj, rj Маленькому Слонику необходимо посчитать количество таких чисел x, что число x встречается ровно x раз среди чисел alj, alj + 1, ..., arj.

Помогите Маленькому Слонику посчитать ответы на все запросы.

Входные данные

В первой строке записаны через пробел два целых числа n и m (1 ≤ n, m ≤ 105) — размер массива a и количество запросов к нему. В следующей строке записаны n целых положительных чисел через пробел a1, a2, ..., an (1 ≤ ai ≤ 109). Следующие m строк содержат описания запросов, по одному на строку. В j-ой из этих строк содержится описание j-го запроса — два целых числа через пробел lj и rj (1 ≤ lj ≤ rj ≤ n).

Выходные данные

В m строках выведите m целых чисел — ответы на запросы. В j-ой строке должен содержаться ответ на j-ый запрос.


Примеры
№Входные данныеВыходные данные
1 7 2
3 1 2 2 3 3 7
1 7
3 4 
3
1

time 4000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет