# One Occurrence

## 题意翻译

**题目大意：** 给定一个长度为 $n$ 的序列，$q$ 次询问，每次询问给定一个区间 $[l,r]$，如果这个区间里存在只出现一次的数，输出这个数（如果有多个就输出任意一个），没有就输出 $0$。 $1 \le n,q \le 5\times 10^5$。 **输入格式：** 第一行一个整数 $n$。 接下来 $1$ 行 $n$ 个小于 $5\times 10^5$ 的正整数表示给出的序列。 下面一行一个整数 $m$。 再下面 $m$ 行，每行两个整数 $l,r$，表示一次询问。 **输入格式：** 共 $m$ 行，每行输出对应的答案。 感谢@守望 提供翻译

## 题目描述

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?

## 输入输出格式

### 输入格式

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$ ).

### 输出格式

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.

## 输入输出样例

### 输入样例 #1

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


### 输出样例 #1

4
0