Card Game
Randias 正在玩纸牌游戏,每张牌上写着一个数。给定手中按顺序排列的牌 a1,a2,…,am,他维护一个最初为空的牌序列。第 i 次操作把第 i 张牌(数字为 ai)放到序列末尾,然后执行:
- 如果序列中没有其他数字为 ai 的牌,本次操作结束。
- 否则,设原序列中第 j 张牌的数字为 ai。收走从这张牌到刚放入的牌之间的全部牌,包括两端这两张牌。
任意时刻序列中的数字互不相同,因此上述第 j 张牌唯一。
例如 a=[2,1,3,1,2,3],初始序列为 []:
- 第一次后为 [2];
- 第二次后为 [2,1];
- 第三次后为 [2,1,3];
- 第四次收走 [1,3,1],剩余 [2];
- 第五次收走 [2,2],剩余 [];
- 第六次后剩余 [3]。
现在有 n 张牌 a1,…,an,以及 q 次询问。第 i 次询问给出区间 [ℓi,ri],问只将 aℓi,aℓi+1,…,ari 作为初始牌序列进行上述游戏,最后剩下多少张牌。
必须按给定顺序在线回答:下一次询问需要使用上一次的答案解码。
输入格式
第一行包含整数 n,q(1≤n,q≤3⋅105)。
第二行包含 n 个整数 a1,…,an(1≤ai≤n)。
接下来 q 行,每行包含两个整数 ℓi′,ri′(0≤ℓi′,ri′≤2n)。设上一次询问的答案为 lastans,则实际区间为
$$\ell_i=\ell'_i\mathbin{\oplus}\mathrm{lastans},\qquad
r_i=r'_i\mathbin{\oplus}\mathrm{lastans},$$
其中 ⊕ 表示按位异或。第一次询问前 lastans = 0。保证解码后 1≤ℓi≤ri≤n。
输出格式
对每次询问输出一行,一个整数,表示该区间游戏结束后剩余的牌数。
原样例 1
5 5
3 3 1 1 1
5 5
3 4
3 3
0 5
3 5
1
2
1
0
1
原样例 2
7 7
2 4 1 2 3 1 2
1 6
0 4
3 3
0 4
0 3
0 6
2 7
2
1
1
1
2
3
0
样例说明
第一个样例解码后的区间依次是 [5,5]、[2,5]、[1,1]、[1,4]、[3,5]。