题目描述

Xhnxhn有一张无限大的纸，刚开始纸上写着n个数字，第i个数字为Ai。他突发奇想，纸上未出现过的最小正整数是多少呢？由于这个问题太简单，他加大了难度，他有Q个操作，每个操作具有格式(op l r)，具体如下：
1. (A l r) 在纸上依次写上一个l，l+1，…r-1，r。
2. (D l r)在纸上依次擦掉一个l，l+1，…r-1，r（保证目前纸上有区间[l，r]中的每一个数）。
对于每个操作，你都要回答纸上未出现过的最小正整数是多少。

输入要求

第一行包含两个数字n(1<=n<=100 000)和Q(1<=Q<=100 000)。
第二行包含n个数字A1,A2,…,An(1<=Ai<=100 000)。
接下来Q行，每行包含op l r(1<=l<=r<=100 000)。

输出要求

对于每一个操作，询问输出操作后纸上未出现过的最小正整数是多少。

输入样例

5 4
1 2 3 4 5
D 4 5
A 2 5
D 2 3
D 1 2

输出样例

4
6
6
1

提示

操作1：纸上数字为[1,2,3]，未出现过的最小正整数为4。
操作2：纸上数字为[1,2,3,2,3,4,5]，未出现过的最小正整数为6。
操作3：纸上数字为[1,2,3,4,5]，未出现过的最小正整数为6。
操作4：纸上数字为[3,4,5]，未出现过的最小正整数为1。

来源

NBU OJ