Дима и массив

Диме не дарили массив $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$.