Дима и массив

문제

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

Дима не играет с массивом, не дарит его Пете, не режет на кусочки и не стремится его уничтожить. Дима просто выполняет операции двух видов со своим массивом:

? l r --- узнать MEX мультимножества $\{a_l, a_{l+1}, \ldots, a_r\}$
! i x --- присвоить $a_i$ значение $x$ $(0 \leq x \leq n)$

MEX мультимножества чисел $\{a_1, a_2, \ldots, a_k\}$ --- это минимальное целое $t \ge 0$ такое, что $t \ne a_i$ для всех $1 \leq i \leq k$.

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

입력

Первая строка содержит два целых числа $n$ и $q$ ($1 \leq n \leq 500\,000, 1 \leq q \leq 250\,000$) --- размер массива, который есть у Димы и количество операций, соответственно.

Вторая строка содержит $n$ целых чисел $a_i$ ($0 \leq a_i \leq n$) --- массив Димы до начала операций.

Каждая из следующих $q$ строк содержит описание одной операции в формате, описанном выше.

Гарантируется, что суммарно Дима сделал не более $50\,000$ операций изменения массива.

Элементы массива пронумерованы, начиная с $1$.

출력

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

힌트

В примере запросы выглядят следующим образом:

Изначально массив равен $[4, 1, 0, 2, 2, 3]$
В первом запросе считается MEX от $\{4, 1, 0, 2, 2, 3\}$ и он равен $5$.
Во втором запросе считается MEX от $\{2, 2, 3\}$ и он равен $0$.
В третьем запросе считается MEX от $\{1, 0, 2, 2\}$ и он равен $3$.
В четвёртом запросе считается MEX от $\{1, 0, 2, 2, 3\}$ и он равен $4$.
Пятый запрос меняет массив. Теперь он равен $[4, 1, 3, 2, 2, 3]$.
В шестом запросе считается MEX от всего массива и он равен $0$.
Седьмой запрос меняет массив. Теперь он равен $[4, 1, 3, 0, 2, 3]$.
В восьмом запросе снова считается MEX от всего массива и теперь он равен $5$.