$n$ 个柜子，每个柜子里都摆放了一个物品，第 $i$ 个柜子里的物品编号为 $a_i$。

请维护物品放置信息，以实现下面的两个操作：

• 1 x，取走第 $x$ 个柜子里的物品，保证此时这个柜子里的物品还在。
• 2 l r，询问第 $l$ 到第 $r$ 个柜子未被取走的物品中是否有两个物品编号相同。

第一行以空格分隔的两个正整数 $n,q \ (1 \leq n,q \leq 5 \times 10^5)$。

接下来一行 $n$ 个正整数 $a_i \ (1 \leq a_i \leq 10^6)$。

接下来 $q$ 行每行一个操作，格式见题目描述。数据保证 $1\leq x,l \leq r \leq n$。

对于每个询问，输出一行一个整数，如果在指定的区间内有两个物品编号相同则输出 $1$，否则输出 $0$。