markdown

F. 恰好出现一次的数

时间限制：每个测试点 $3$ 秒
内存限制：每个测试点 $768$ MB
输入：标准输入
输出：标准输出

给定一个包含 $n$ 个整数的数组 $a$，以及 $q$ 个询问。第 $i$ 个询问由两个整数 $l_i$ 和 $r_i$ 表示。对于每个询问，你需要找出在数组 $a$ 的子数组 $a[l_i \ldots r_i]$（子数组指数组中一段连续的子区间）中恰好出现一次的任意一个整数。

例如，若 $a = [1,1,2,3,2,4]$，对于询问 $(l_i=2, r_i=6)$，我们关注的子数组是 $[1,2,3,2,4]$，可能的答案有 $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$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 个询问（$1 \le l_i \le r_i \le n$）。

输出

对于每个询问，按如下方式回答：

• 如果子数组 $a[l_i \ldots r_i]$ 中不存在恰好出现一次的整数，则输出 $0$。
• 否则，输出任意一个这样的整数。

样例

输入

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

输出

4
0