众数

有一个长度为 $ n $ 的整数序列 $ a_1,a_2,\cdots,a_n $，序列中每个元素 $ a_i $ 都在 $ 1\sim n $ 中**等概率随机**生成。

定义一个序列 $ b_1,b_2,\cdots,b_m $ 的价值 $ \operatorname{val}(b_1,b_2,\cdots,b_m) $ 为其所有连续子序列的最大值的众数（即出现次数最大的数），当有多个众数时选择值最大的众数。

给出 $ q $ 次询问，每次询问给定两个整数 $ l,r $，问 $ \operatorname{val}(a_{l},a_{l+1},\cdots,a_r) $。

本题单个测试点内包含多组测试数据。

第一行一个整数 $ T(1\leq T\leq 3) $，表示数据组数。

对于每组数据，第一行两个整数 $ n,q $ $ (1\leq n,q\leq 2\times 10^5) $，分别表示序列长度和询问次数。

第二行 $ n $ 个整数 $ a_1,a_2,\cdots,a_n $ $ (1\leq a_i\leq n) $，表示序列。

接下来 $ q $ 行，每行两个整数 $ l_i,r_i $ $ (1\leq l_i\leq r_i\leq n) $，表示一次询问。

对于每组数据，由于输出很大，假设原来第 $i$ 个询问的答案是 $x_i$，你只需要输出一行一个整数：
$$
\bigoplus_{i=1}^{q}i\cdot x_i
$$
即 $i$ 和 $x_i$ 乘积的异或和即可。

1
5 3
1 2 2 1 3
1 5
2 3
3 5

15

三次询问的答案分别为 $2,2,3$。

2024“钉耙编程”中国大学生算法设计超级联赛（1）