English · Original
Chinese · Translation
Formal · Original
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?
## Input
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$).
## Output
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.
[samples]
给你一个包含 $n$ 个整数的数组 $a$，以及 $q$ 个查询。第 $i$ 个查询由两个整数 $l_i$ 和 $r_i$ 表示。对于每个查询，你需要找到在子数组 $a[l_i \dots 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 ]$，其中没有元素恰好出现一次。
你能回答所有查询吗？
第一行包含一个整数 $n$（$1 lt.eq n lt.eq 5 dot.op 10^5$）。
第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 5 dot.op 10^5$）。
第三行包含一个整数 $q$（$1 lt.eq q lt.eq 5 dot.op 10^5$）。
接下来 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 个查询（$1 lt.eq l_i lt.eq r_i lt.eq n$）。
按以下方式回答查询：
如果在从索引 $l_i$ 到 $r_i$ 的子数组中没有整数恰好出现一次，则输出 $0$；否则输出任意一个这样的整数。
## Input
第一行包含一个整数 $n$（$1 lt.eq n lt.eq 5 dot.op 10^5$）。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 5 dot.op 10^5$）。第三行包含一个整数 $q$（$1 lt.eq q lt.eq 5 dot.op 10^5$）。接下来 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 个查询（$1 lt.eq l_i lt.eq r_i lt.eq n$）。
## Output
按以下方式回答查询：如果在从索引 $l_i$ 到 $r_i$ 的子数组中没有整数恰好出现一次，则输出 $0$；否则输出任意一个这样的整数。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the array.
Let $ a = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i \in \mathbb{Z}^+ $.
Let $ q \in \mathbb{Z}^+ $ be the number of queries.
For each query $ j \in \{1, \dots, q\} $, let $ (l_j, r_j) \in \mathbb{Z}^2 $ denote the subarray bounds, with $ 1 \le l_j \le r_j \le n $.
**Constraints**
1. $ 1 \le n \le 5 \cdot 10^5 $
2. $ 1 \le a_i \le 5 \cdot 10^5 $ for all $ i \in \{1, \dots, n\} $
3. $ 1 \le q \le 5 \cdot 10^5 $
4. $ 1 \le l_j \le r_j \le n $ for all $ j \in \{1, \dots, q\} $
**Objective**
For each query $ j \in \{1, \dots, q\} $, define the subarray $ S_j = \{a_i \mid l_j \le i \le r_j\} $.
Let $ f_j(x) = |\{i \mid l_j \le i \le r_j \text{ and } a_i = x\}| $ be the frequency of integer $ x $ in $ S_j $.
Find any integer $ x \in \mathbb{Z}^+ $ such that $ f_j(x) = 1 $, or output $ 0 $ if no such $ x $ exists.
API Response (JSON)
{
"problem": {
"name": "F. One Occurrence",
"description": {
"content": "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 **e",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 786432
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1000F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 **e...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "给你一个包含 $n$ 个整数的数组 $a$，以及 $q$ 个查询。第 $i$ 个查询由两个整数 $l_i$ 和 $r_i$ 表示。对于每个查询，你需要找到在子数组 $a[l_i \\dots r_i]$ 中恰好出现一次的任意一个整数（子数组是数组的连续子段）。例如，如果 $a = [ 1, 1, 2, 3, 2, 4 ]$，那么对于查询 $(l_i = 2, r_i = 6)$，我们关心的子数组是 ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array. \nLet $ a = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in \\mathbb{Z}^+ $. \nLet $ q \\in \\mathbb{Z}^+ $ be...",
"is_translate": false,
"language": "Formal"
}
]
}