F. Экзотические запросы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

AquaMoon дала RiverHamster последовательность целых чисел $$$a_1,a_2,\dots,a_n$$$, а RiverHamster задал вам $$$q$$$ запросов. Каждый запрос характеризуется двумя целыми числами $$$l$$$ и $$$r$$$.

При ответе на каждый запрос вы можете выбрать любой непрерывный отрезок последовательности и вычесть из всех его элементов одно и то же неотрицательное число. Выполнять эту операцию можно несколько (возможно, ноль) раз. Однако нельзя выбрать два пересекающихся отрезка, которые были бы не вложены друг в друга. Ваша задача — превратить в $$$0$$$ все числа, у которых изначальное значение лежало в диапазоне $$$[l, r]$$$. Сделать это нужно за наименьшее число операций.

Обратите внимание, что запросы независимы, числа в массиве возвращаются к своим первоначальным значениям между запросами.

Формально, для каждого запроса нужно найти наименьшее $$$m$$$, для которого существует последовательность $$$\{(x_j,y_j,z_j)\}_{j=1}^{m}$$$, удовлетворяющая следующим условиями:

  • для любого $$$1 \le j \leq m$$$ выполняется $$$z_j \ge 0$$$ и $$$1 \le x_j \le y_j \leq n$$$ (здесь $$$[x_j, y_j]$$$ представляют отрезки в последовательности);
  • для любых $$$1 \le j < k \le m$$$ выполняется $$$[x_j,y_j]\subseteq[x_{k},y_{k}]$$$, $$$[x_k,y_k]\subseteq[x_{j},y_{j}]$$$, или $$$[x_j,y_j]\cap[x_{k},y_{k}]=\varnothing$$$;
  • для любого $$$1 \le i \le n$$$, такого что $$$l \le a_i \leq r$$$, выполняется $$$$$${\large a_i = \sum\limits_{\substack {1 \le j \le m \\ x_j \le i \le y_j}} z_j. }$$$$$$
Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1\le n,q\le 10^6$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

Каждая из следующих $$$q$$$ строк содержит по два целых числа $$$l$$$ и $$$r$$$ ($$$1\le l\le r\le n$$$), характеризующий очередной запрос.

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

Выведите ответ на каждый запрос на отдельной строке.

Примеры
Входные данные
10 8
1 6 2 3 2 6 3 10 1 2
1 10
2 2
3 3
2 3
1 3
3 6
4 6
5 5
Выходные данные
8
1
1
3
5
3
1
0
Входные данные
3 1
1 3 2
1 3
Выходные данные
3
Примечание

В первом наборе входных данных рассмотрим второй запрос: $$$l = 2$$$, $$$r = 2$$$. Элементы, которые нужно обнулить, суть $$$[a_3, a_5, a_{10}] = [2, 2, 2]$$$. Достаточно применить последовательность операций $$$\{(2, 10, 2)\}$$$.

В четвёртом запросе $$$l = 2$$$, $$$r = 3$$$. Обнулить нужно элементы $$$[a_3, a_4, a_5, a_7, a_{10}] = [2, 3, 2, 3, 2]$$$. Достаточно применить последовательность операций $$$\{(1, 10, 2), (4, 4, 1), (7, 7, 1)\}$$$.

Во втором наборе входных данных можно заметить, что последовательность операций $$$\{(1, 2, 1), (2, 3, 2)\}$$$ не является допустимой, потому что два используемых отрезка пересекаются, но не вложены один в другой.