← 返回题目列表

Codeforces · 1771/F

F. Hossam 和范围最小查询

中文机器翻译题面 查看原题

Hossam 为您提供长度为 $$$n$$$ 的整数序列 $$$a_1, \, a_2, \, \dots, \, a_n$$$。此外,他会给你 $$$q$$$ 类型的 $$$(l, \, r)$$$ 查询。对于每个查询,考虑元素 $$$a_l, \, a_{l + 1}, \, \dots, \, a_r$$$。 Hossam 想要知道该序列中最小的数字,以便它在此序列中出现奇数次。

在处理下一个查询之前,您需要计算每个查询的答案。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$),即序列的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, \, a_2, \, \dots, \, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

第三行包含一个整数$$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$),即查询次数。

接下来的 $$$q$$$ 行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$0 \le a, \, b \le 2 \cdot 10^9$$$),这些数字用于对查询进行编码。

设 $$$\mathrm{ans}_i$$$ 为第 $$$i$$$ 个查询的答案,$$$\mathrm{ans}_0$$$ 为零。那么 $$$$$$l_i = a_i \oplus \mathrm{ans}_{i - 1},$$$$$$$$$$$r_i = b_i \oplus \mathrm{ans}_{i - 1},$$$$$$ 其中 $$$l_i, \, r_i$$$ 是第 $$$i$$$ 查询的参数,$$$\oplus$$$ 表示第按位异或运算。保证$$$1 \le l \le r \le n$$$。

输出

对于每个查询,打印在序列的给定段上出现奇数次的最小数字。

如果没有这样的数字,则打印$$$0$$$。

示例

输入 #1

5
1 2 1 2 2
6
1 2
0 2
0 6
0 5
2 2
3 7

输出 #1

1
2
1
0
2
2

输入 #2

10
51 43 69 48 23 52 48 76 19 55
10
1 1
57 57
54 62
20 27
56 56
79 69
16 21
18 30
25 25
62 61

输出 #2

51
55
19
48
76
19
23
19
55
19

注意

在示例中,

$$$$$$l_1 = 1、\、r_1 = 2、$$$$$$$$$$$$l_2 = 1、\、r_2 = 3、$$$$$ $$$$$$l_3 = 2、\、r_3 = 4、$$$$$$ $$$$$$l_4 = 1、\、r_4 = 4、$$$$$$$$$$$$l_5 = 2、\、r_5 = 2、$$$$$$$$$$$$l_6 = 1、\、r_6 = 5。$$$$$$