← 返回题目列表

Codeforces · 1000/F

F. 一次出现

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$,并对其进行 $$$q$$$ 查询。第 $$$i$$$ 查询由两个整数 $$$l_i$$$ 和 $$$r_i$$$ 表示。对于每个查询,您必须找到从索引 $$$l_i$$$ 到索引 $$$r_i$$$ 的 $$$a$$$ 子数组中恰好出现一次的任何整数(子数组是数组的连续子段)。例如,如果 $$$a = [1, 1, 2, 3, 2, 4]$$$,那么对于查询 $$$(l_i = 2, r_i = 6)$$$,我们感兴趣的子数组是 $$$[1, 2, 3, 2, 4]$$$,可能的答案是 $$$1$$$、$$$3$$$ 和 $$$4$$$;对于查询 $$$(l_i = 1, r_i = 2)$$$,我们感兴趣的子数组是 $$$[1, 1]$$$,并且不存在恰好出现一次的此类元素。

您能回答所有问题吗?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$)。

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

第三行包含一个整数$$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$)。

然后是 $$$q$$$ 行,第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ 表示第 $$$i$$$ 查询($$$1 \le l_i \le r_i \le n$$$)。

输出

回答问题如下:

如果没有整数在从索引 $$$l_i$$$ 到索引 $$$r_i$$$ 的子数组中恰好出现一次,则打印 $$$0$$$。否则打印任何这样的整数。

示例

输入 #1

6
1 1 2 3 2 4
2
2 6
1 2

输出 #1

4
0