G. Мерзость отрезков
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Андрей вспомнил, что у него в шкафу есть $$$n$$$ кубиков, пронумерованных от $$$1$$$ до $$$n$$$. На кубике с номером $$$i$$$ изначально записано целое число $$$a_i$$$. Он выложил их в ряд в порядке возрастания номеров: сначала лежит кубик с номером $$$1$$$, затем кубик с номером $$$2$$$ и так далее, а в конце лежит кубик с номером $$$n$$$.

Для некоторого отрезка подряд идущих кубиков $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$) назовем целое число $$$d\ (0 \le d \le r-l)$$$ мерзким, если $$$\min(a_l, a_{l+1}, \ldots, a_{l+d}) = d$$$.

Андрей очень любопытен, поэтому он хочет выполнить $$$q$$$ действий одного из двух видов:

  1. Изменить число $$$a_i$$$, записанное на $$$i$$$-м кубике, на $$$x$$$.
  2. Определить мерзость отрезка $$$[l,\ r]\ (1 \le l \le r \le n)$$$. Под мерзостью отрезка подразумевается количество мерзких чисел $$$d\ (0 \le d \le r-l)$$$ для данного отрезка.

Андрей не смог придумать, как быстро обрабатывать эти запросы, и обратился к Вам за помощью. Помогите ему выполнить описанные выше действия!

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

В первой строке содержится целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ — количество наборов входных данных.

Во первой строке каждого набора содержатся два целых числа $$$n$$$ и $$$q$$$ $$$(1 \le n, q \le 2 \cdot 10^5)$$$ — количество кубиков и количество действий соответственно.

В следующей строке содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 2 \cdot 10^5)$$$ — изначальные числа, записанные на кубиках.

Следующие $$$q$$$ строк описывают действия, которые необходимо выполнить.

Каждая строка начинается с целого числа $$$idx$$$ $$$(1 \le idx \le 2)$$$ — тип действия.

Если $$$idx = 1$$$, то далее следуют два целых числа $$$i$$$ $$$(1 \le i \le n)$$$ и $$$x$$$ $$$(1 \le x \le 2 \cdot 10^5)$$$ — описание действия первого вида.

Если $$$idx = 2$$$, то далее следуют два целых числа $$$l$$$ и $$$r$$$ $$$(1 \le l \le r \le n)$$$ — описание действия второго вида.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$, а также сумма $$$q$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных на каждое действие второго типа выведите целое число, обозначающее мерзость отрезка.

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