题目描述

Dima 并不是生日时收到数组 $a$ 的，也不是买来的，更不是在路上捡到的；这个由 $n$ 个整数组成的数组只是一直存在于他那里，而 Dima 对它的来历也并不感兴趣。

Dima 不拿这个数组玩，不把它送给 Petya，不把它切成碎片，也不想毁掉它。Dima 只是对数组执行两种操作：

• ? l r：询问多重集合 $\{a_l,a_{l+1},\ldots,a_r\}$ 的 MEX；
• ! i x：将 $a_i$ 赋值为 $x$，其中 $0 \le x \le n$。

一个多重集合 $\{a_1,a_2,\ldots,a_k\}$ 的 MEX 定义为最小的整数 $t \ge 0$，使得对于所有 $1 \le i \le k$，都有 $t \ne a_i$。

事实上，Dima 并不喜欢亲自执行这些操作。他只关心第一类操作的结果。请你帮 Dima 完成这些操作。

输入格式

第一行包含两个整数 $n,q$，表示数组长度和操作数。

第二行包含 $n$ 个整数 $a_i$，表示操作开始前的数组。

接下来 $q$ 行，每行描述一个操作，格式如题目描述所示。

满足：

$$1 \le n \le 500000,\quad 1 \le q \le 250000,\quad 0 \le a_i \le n.$$

保证修改操作 ! 的总数不超过 $50000$。

数组下标从 $1$ 开始。

输出格式

对于每个第一类操作 ? l r，输出一个整数，表示对应多重集合的 MEX。答案按输入中查询出现的顺序输出。

样例

6 8
4 1 0 2 2 3
? 1 6
? 4 6
? 2 5
? 2 6
! 3 3
? 1 6
! 4 0
? 1 6

5
0
3
4
0
5

样例解释

样例中的操作如下：

• 初始数组为 $[4,1,0,2,2,3]$。
• 第一次查询求 $\{4,1,0,2,2,3\}$ 的 MEX，答案为 $5$。
• 第二次查询求 $\{2,2,3\}$ 的 MEX，答案为 $0$。
• 第三次查询求 $\{1,0,2,2\}$ 的 MEX，答案为 $3$。
• 第四次查询求 $\{1,0,2,2,3\}$ 的 MEX，答案为 $4$。
• 第五次操作修改数组，现在数组为 $[4,1,3,2,2,3]$。
• 第六次查询求整个数组的 MEX，答案为 $0$。
• 第七次操作修改数组，现在数组为 $[4,1,3,0,2,3]$。
• 第八次查询再次求整个数组的 MEX，答案为 $5$。

子任务

组别	分数	$n$	$q$	$a_i,x$	必须通过的组	说明
0		—		—	—	样例测试
1	11	$\le 100$			0
2	8	$\le 5000$			0,1
3	12	—		$\le 10$	0
4	19			—	—	没有修改操作
5	5	$\le 100000$			0–2
6		$\le 150000$			0–2,5
7		$\le 200000$			0–2,5,6
8		$\le 250000$	—		0–2,5–7
9	6	$\le 300000$			0–2,5–8	离线测试
10		$\le 350000$			0–2,5–9
11		$\le 400000$			0–2,5–10
12		$\le 450000$			0–2,5–11
13		—			0–12