给定一个由 $$$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