Знаете ли вы компанию Just Odd Inventions? Её деятельность заключается в том, чтобы делать «просто странные изобретения». Далее будем для краткости называть её компанией JOI.

Компания JOI решила нанять новых сотрудников, чтобы расширить свой бизнес.

Есть $N$ кандидатов на работу. Кандидаты пронумерованы от $1$ до $N$, и каждому из них сопоставлено целое число, называемое оценкой.

При этом найме будут приняты все кандидаты, чья оценка не меньше некоторого значения. Новых сотрудников разделят на несколько групп. Группы новых сотрудников формируются так, чтобы выполнялось следующее условие:

• Если кандидат $a$ и кандидат $b$ ($a<b$) оба приняты на работу, то эти сотрудники входят в одну группу тогда и только тогда, когда все кандидаты $c$ ($a \le c \le b$) приняты на работу.

Вы, как сотрудник отдела кадров компании JOI, должны оценить количество групп, которые будут созданы при этом найме, последовательно обработав в общей сложности $M$ запросов. Запрос с номером $j$ относится к одному из двух следующих типов:

• Найти количество групп, которые образуются, если принять всех кандидатов с оценкой не меньше $B_j$. Запрос этого типа называется запросом ответа.
• Изменить оценку кандидата $C_j$ на $D_j$. Запрос этого типа называется запросом обновления.

Задача

Напишите программу, которая по информации о $M$ запросах находит количество групп для каждого запроса ответа.

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

Считайте следующие данные со стандартного ввода.

• Первая строка содержит целые числа $N,M$, разделённые пробелом. Это означает, что есть $N$ кандидатов на работу и вам предстоит обработать $M$ запросов.
• Строка с номером $i$ ($1 \le i \le N$) среди следующих $N$ строк содержит целое число $A_i$. Это означает, что до обработки запросов оценка кандидата $i$ равна $A_i$.

• Строка с номером $j$ ($1 \le j \le M$) среди следующих $M$ строк содержит два или три целых числа, разделённых пробелами. Обозначим первое целое число через $T_j$. Тогда содержимое строки имеет один из следующих видов:

  1. Если $T_j=1$, строка содержит целые числа $T_j,B_j$, разделённые пробелом. Это означает, что запрос с номером $j$ является запросом ответа: требуется найти количество групп, которые образуются, если принять всех кандидатов с оценкой не меньше $B_j$.
  2. Если $T_j=2$, строка содержит целые числа $T_j,C_j,D_j$, разделённые пробелами. Это означает, что запрос с номером $j$ является запросом обновления: требуется изменить оценку кандидата $C_j$ на $D_j$.

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

Для каждого запроса ответа выведите в стандартный вывод количество групп в порядке запросов, по одному числу в строке.

Ограничения

Все входные данные удовлетворяют следующим условиям.

• $1 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le T_j \le 2$ ($1 \le j \le M$).
• $1 \le B_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• $1 \le C_j \le N$ ($1 \le j \le M$).
• $1 \le D_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• Существует хотя бы одно $j$ ($1 \le j \le M$), для которого $T_j=1$.

Подзадачи

Подзадача 1 [10 баллов]

Выполняются следующие условия.

• $N \le 2\,000$.
• $M \le 2\,000$.

Подзадача 2 [30 баллов]

• Выполняется $T_j=1$ ($1 \le j \le M$).

Подзадача 3 [60 баллов]

Дополнительных ограничений нет.

Примеры

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

5 4
8
6
3
5
4
1 5
2 4 1
1 5
1 3

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

2
1
2

Примечание

1. Первый запрос является запросом ответа. Если принять кандидатов 1, 2 и 4, чьи оценки не меньше 5, образуются две группы: группа из кандидатов 1 и 2 и группа из кандидата 4. Поэтому выводится 2.
2. Второй запрос является запросом обновления. Оценка кандидата 4 изменяется на 1.
3. Третий запрос является запросом ответа. Если принять кандидатов 1 и 2, чьи оценки не меньше 5, образуется одна группа из кандидатов 1 и 2. Поэтому выводится 1.
4. Четвёртый запрос является запросом ответа. Если принять кандидатов 1, 2, 3 и 5, чьи оценки не меньше 3, образуются две группы: группа из кандидатов 1, 2 и 3 и группа из кандидата 5. Поэтому выводится 2.

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

7 5
13
19
1
15
13
1
19
1 20
1 1
1 6
1 11
1 17

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

0
1
3
3
2

Примечание

Второй пример удовлетворяет ограничениям подзадачи 2.

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

10 5
8
10
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16

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

2
1
0