CF1000F.One Occurrence

You are given an array $a$ consisting of $n$ integers, and $q$ queries to it. $i$-th query is denoted by two integers $l_i$ and $r_i$. For each query, you have to find any integer that occurs exactly once in the subarray of $a$ from index $l_i$ to index $r_i$ (a subarray is a contiguous subsegment of an array). For example, if $a = [1, 1, 2, 3, 2, 4]$, then for query $(l_i = 2, r_i = 6)$ the subarray we are interested in is $[1, 2, 3, 2, 4]$, and possible answers are $1$, $3$ and $4$; for query $(l_i = 1, r_i = 2)$ the subarray we are interested in is $[1, 1]$, and there is no such element that occurs exactly once.

Can you answer all of the queries?

给你一个包含 $n$ 个整数的数组 $a$，以及 $q$ 个对该数组的查询。第 $i$ 个查询由两个整数 $l_i$ 和 $r_i$ 表示。对于每个查询，你需要在数组 $a$ 从下标 $l_i$ 到下标 $r_i$ 的子数组（子数组是数组的一个连续子段）中，找出任意一个恰好出现一次的整数。例如，若 $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]$，此时不存在恰好出现一次的元素。

你能回答所有这些查询吗？

The first line contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5 \cdot 10^5$).

The third line contains one integer $q$ ($1 \le q \le 5 \cdot 10^5$).

Then $q$ lines follow, $i$-th line containing two integers $l_i$ and $r_i$ representing $i$-th query ($1 \le l_i \le r_i \le n$).

第一行包含一个整数 $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$）。

Answer the queries as follows:

If there is no integer such that it occurs in the subarray from index $l_i$ to index $r_i$ exactly once, print $0$. Otherwise print any such integer.

按以下方式回答查询：

如果在从索引 $l_i$ 到索引 $r_i$ 的子数组中，不存在恰好出现一次的整数，则输出 $0$；否则，输出任意一个满足条件的整数。