Вам надано послідовність ~A=(A_1 ​ ,A_2 ​ ,…,A_N ​ )~ довжини ~N~.

Обробіть ~Q~ запитів у тому порядку, у якому вони надані. Кожен запит належить до одного з наступних двох типів:

• Тип 1: 1 p x. Змініть значення ~A_p~ ​ на ~x~.
• Тип 2: 2 l r. Виведіть кількість входжень другого за величиною значення в (~A_l ​,A_{l+1} ​ ,…,A_r ​)~. Точніше, виведіть кількість цілих чисел ~i~, які задовольняють ~l≤i≤r~ так, що серед ~A_l ​,A_{l+1} ,…,A_r~ ​ існує рівно одне окреме значення, більше за ~A_i~ ​.

Обмеження

• ~1≤N,Q≤2×10^5~
• ~1≤A_i ​ ≤10^9~
• Для запитів типу 1 ~1≤p≤N~.
• Для запитів типу 1 ~1≤x≤10^9~.
• Для запитів типу 2, ~1≤l≤r≤N~.
• Є принаймні один запит типу 2.
• Усі вхідні значення є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа ~N,Q~.

Наступний   рядок містить ~N~ цілих чисел ~A_i~.

Наступні  ~Q~ рядків містять запити описаних типів.

Формат вихідних даних

Нехай ~q~ буде кількістю запитів типу 2.

Вивести ~q~ рядків. ~I~-й рядок має містити відповідь на ~i~-й запит 2-го типу.

Приклад вхідних даних

5 4
3 3 1 4 5
2 1 3
2 5 5
1 3 3
2 2 4

Приклад вихідних даних

1
0
2

Спочатку A=(3,3,1,4,5).

• Для першого запиту другим найбільшим значенням у (3,3,1) є 1, яке зʼявляється один раз у 3,3,1, тому виведіть 1.
• Для другого запиту в (5) немає другого найбільшого значення, тому виведіть 0.
• Третій запит створює A=(3,3,3,4,5).
• Для четвертого запиту другим найбільшим значенням у (3,3,4) є 3, яке зʼявляється двічі в 3,3,4, тому надрукуйте 2.

Приклад вхідних даних

1 1
1000000000
2 1 1

Приклад вихідних даних

0

Приклад вхідних даних

8 9
2 4 4 3 9 1 1 2
1 5 4
2 7 7
2 2 6
1 4 4
2 2 5
2 2 7
1 1 1
1 8 1
2 1 8

Приклад вихідних даних

0
1
0
2
4