C. Уничтожение фиксированных точек
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a_1, \ldots, a_n$$$ из $$$n$$$ положительных целых чисел. За одну операцию можно выбрать индекс $$$i$$$, удовлетворяющий $$$a_i = i$$$, и удалить $$$a_i$$$ из массива (после удаления остальные части массива соединяются).

Вес $$$a$$$ определяется как максимальное количество элементов, которые можно удалить.

Вы должны ответить на $$$q$$$ независимых запросов $$$(x, y)$$$: после замены первых $$$x$$$ элементов $$$a$$$ и последних $$$y$$$ элементов $$$a$$$ на $$$n+1$$$ (делая их удаление невозможным), чему будет равен вес $$$a$$$?

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

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$)  — длину массива и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq n$$$) — элементы массива.

$$$i$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$x$$$ и $$$y$$$ ($$$x, y \ge 0$$$ и $$$x+y < n$$$).

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

Выведите $$$q$$$ строк, $$$i$$$-я строка должна содержать единственное целое число  — ответ на $$$i$$$-й запрос.

Примеры
Входные данные
13 5
2 2 3 9 5 4 6 5 7 8 3 11 13
3 1
0 0
2 4
5 0
0 12
Выходные данные
5
11
6
1
0
Входные данные
5 2
1 4 1 2 4
0 0
1 0
Выходные данные
2
0
Примечание

Объяснение первого запроса:

После того, как первые $$$x = 3$$$ и последние $$$y = 1$$$ элементов стало невозможно удалить, $$$a$$$ становится равным $$$[\times, \times, \times, 9, 5, 4, 6, 5, 7, 8, 3, 11, \times]$$$ (для наглядности мы представляем $$$14$$$ как $$$\times$$$).

Вот стратегия, которая удаляет $$$5$$$ элементов (удаленный элемент окрашен в красный цвет):

  • $$$[\times, \times, \times, 9, \color{red}{5}, 4, 6, 5, 7, 8, 3, 11, \times]$$$
  • $$$[\times, \times, \times, 9, 4, 6, 5, 7, 8, 3, \color{red}{11}, \times]$$$
  • $$$[\times, \times, \times, 9, 4, \color{red}{6}, 5, 7, 8, 3, \times]$$$
  • $$$[\times, \times, \times, 9, 4, 5, 7, \color{red}{8}, 3, \times]$$$
  • $$$[\times, \times, \times, 9, 4, 5, \color{red}{7}, 3, \times]$$$
  • $$$[\times, \times, \times, 9, 4, 5, 3, \times]$$$ (конечное состояние)

Невозможно удалить более $$$5$$$ элементов, поэтому вес составляет $$$5$$$.