#P18510. Card Game

Card Game

Card Game

Randias 正在玩纸牌游戏,每张牌上写着一个数。给定手中按顺序排列的牌 a1,a2,…,ama_1,a_2,\ldots,a_m,他维护一个最初为空的牌序列。第 ii 次操作把第 ii 张牌(数字为 aia_i)放到序列末尾,然后执行:

  • 如果序列中没有其他数字为 aia_i 的牌,本次操作结束。
  • 否则,设原序列中第 jj 张牌的数字为 aia_i。收走从这张牌到刚放入的牌之间的全部牌,包括两端这两张牌。

任意时刻序列中的数字互不相同,因此上述第 jj 张牌唯一。

例如 a=[2,1,3,1,2,3]a=[2,1,3,1,2,3],初始序列为 [][]:

  1. 第一次后为 [2][2];
  2. 第二次后为 [2,1][2,1];
  3. 第三次后为 [2,1,3][2,1,3];
  4. 第四次收走 [1,3,1][1,3,1],剩余 [2][2];
  5. 第五次收走 [2,2][2,2],剩余 [][];
  6. 第六次后剩余 [3][3]。

现在有 nn 张牌 a1,…,ana_1,\ldots,a_n,以及 qq 次询问。第 ii 次询问给出区间 [ℓi,ri][\ell_i,r_i],问只将 aℓi,aℓi+1,…,aria_{\ell_i},a_{\ell_i+1},\ldots,a_{r_i} 作为初始牌序列进行上述游戏,最后剩下多少张牌。

必须按给定顺序在线回答:下一次询问需要使用上一次的答案解码。

输入格式

第一行包含整数 n,qn,q(1≤n,q≤3⋅1051\le n,q\le3\cdot10^5)。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n(1≤ai≤n1\le a_i\le n)。

接下来 qq 行,每行包含两个整数 ℓi′,ri′\ell'_i,r'_i(0≤ℓi′,ri′≤2n0\le\ell'_i,r'_i\le2n)。设上一次询问的答案为 lastans,则实际区间为

$$\ell_i=\ell'_i\mathbin{\oplus}\mathrm{lastans},\qquad r_i=r'_i\mathbin{\oplus}\mathrm{lastans},$$

其中 ⊕\oplus 表示按位异或。第一次询问前 lastans = 0。保证解码后 1≤ℓi≤ri≤n1\le\ell_i\le r_i\le 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][5,5]、[2,5][2,5]、[1,1][1,1]、[1,4][1,4]、[3,5][3,5]。