Недавно, на свой день рождения, Алиса получила массив $$$a_1, a_2, \dots, a_n$$$. Массив ей очень понравился, как ее другу Бобу, которому Алиса его показала.
Однако довольно скоро Боб, как любой хороший друг, попросил Алису выполнить $$$q$$$ операций двух видов над ее массивом:
Помогите Алисе ответить на запросы Боба!
В первой строке заданы два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — размер массива и количество запросов, соответственно.
Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — массив Алисы.
В следующих $$$q$$$ строках заданы по три целых числа. Первое число в $$$i$$$-й строке — это $$$t_i$$$, тип операции $$$i$$$-го запроса ($$$t_i = 1$$$ или $$$t_i = 2$$$).
Если $$$t_i = 1$$$, то следующие два числа — это $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le 10^9$$$), позиция $$$x_i$$$ и новое значение $$$y_i$$$ (нужно присвоить $$$a_{x_i} = y_i$$$).
Если $$$t_i = 2$$$, то следующие два числа — это $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$), границы подмассива, о котором Боб спрашивает Алису в $$$i$$$-м запросе.
Гарантируется, что есть хотя бы один запрос второго типа.
Для каждого запроса $$$2$$$-го типа выведите одно целое число — ответ на данный запрос.
5 6 3 1 4 1 5 2 2 5 2 1 3 1 4 4 2 2 5 1 2 6 2 2 5
6 4 10 7
Для первого запроса ($$$l = 2$$$ и $$$r = 5$$$) неубывающие подмассивы $$$[p,q]$$$ — это $$$[2,2]$$$, $$$[3,3]$$$, $$$[4,4]$$$, $$$[5,5]$$$, $$$[2,3]$$$ и $$$[4,5]$$$.
| Codeforces Round 742 (Div. 2) |
|---|
| Закончено |
