D. Маленький Слоник и массив
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Слоник любит играть с массивами. У него есть массив 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-ый запрос.

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