这是一个交互式问题。在输出每个询问的答案后，你必须立即使用 flush 操作。例如，在 C++ 中你应该使用 fflush(stdout) 或 cout.flush()，在 Java 或 Kotlin 中使用 System.out.flush()，在 Python 中使用 sys.stdout.flush()。

给你一个初始由 $n$ 个整数组成的数组 $a$。你需要处理 $q$ 个以下类型的操作：

• + i x — 在数组 $a$ 的前 $i$ 个元素之后插入整数 $x$（保证在进行此操作时，数组 $a$ 至少有 $i$ 个元素）；
• ? l r — 计算 $a_l, a_{l+1}, \dots, a_r$ 中不同整数的个数。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^5$），分别表示数组 $a$ 的初始元素个数和操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示数组 $a$ 的初始元素。

接下来的每一行包含一个操作，格式为以下两者之一（其中 $n'$ 表示数组 $a$ 的当前大小）：

• + i x（$0 \le i \le n'$；$1 \le x \le n$）；
• ? l r（$1 \le l \le r \le n'$）。

输出格式

对于每个第二种类型的询问，在单独的一行中输出一个整数，表示 $a_l, a_{l+1}, \dots, a_r$ 中不同整数的个数。

在输出任何内容后，请不要忘记刷新输出缓冲区。否则，你可能会得到 "Idleness Limit Exceeded" 的评测结果。

样例

输入样例 1

3 6
1 2 1
? 1 3
+ 0 1
+ 0 1
? 1 3
+ 1 3
? 1 6

输出样例 1

2
1
3