Чи знаєте ви компанію 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