{"raw_statement":[{"iden":"statement","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 **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.\n\nCan you answer all of the queries?"},{"iden":"input","content":"The first line contains one integer $n$ ($1 \\le n \\le 5 \\cdot 10^5$).\n\nThe second line contains $n$ integers $a_1, a_2, \\dots, a_n$ ($1 \\le a_i \\le 5 \\cdot 10^5$).\n\nThe third line contains one integer $q$ ($1 \\le q \\le 5 \\cdot 10^5$).\n\nThen $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$)."},{"iden":"output","content":"Answer the queries as follows:\n\nIf 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."},{"iden":"example","content":"Input\n\n6\n1 1 2 3 2 4\n2\n2 6\n1 2\n\nOutput\n\n4\n0"}],"translated_statement":[{"iden":"statement","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)$，我们关心的子数组是 $[ 1, 2, 3, 2, 4 ]$，可能的答案是 $1$、$3$ 和 $4$；而对于查询 $(l_i = 1, r_i = 2)$，我们关心的子数组是 $[ 1, 1 ]$，其中没有元素恰好出现一次。\n\n你能回答所有查询吗？\n\n第一行包含一个整数 $n$（$1 lt.eq n lt.eq 5 dot.op 10^5$）。\n\n第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 5 dot.op 10^5$）。\n\n第三行包含一个整数 $q$（$1 lt.eq q lt.eq 5 dot.op 10^5$）。\n\n接下来 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示第 $i$ 个查询（$1 lt.eq l_i lt.eq r_i lt.eq n$）。\n\n按以下方式回答查询：\n\n如果在从索引 $l_i$ 到 $r_i$ 的子数组中没有整数恰好出现一次，则输出 $0$；否则输出任意一个这样的整数。"},{"iden":"input","content":"第一行包含一个整数 $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$）。"},{"iden":"output","content":"按以下方式回答查询：如果在从索引 $l_i$ 到 $r_i$ 的子数组中没有整数恰好出现一次，则输出 $0$；否则输出任意一个这样的整数。"}],"sample_group":[],"show_order":[],"formal_statement":"**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 the number of queries.  \nFor 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 $.\n\n**Constraints**  \n1. $ 1 \\le n \\le 5 \\cdot 10^5 $  \n2. $ 1 \\le a_i \\le 5 \\cdot 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\le q \\le 5 \\cdot 10^5 $  \n4. $ 1 \\le l_j \\le r_j \\le n $ for all $ j \\in \\{1, \\dots, q\\} $\n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, q\\} $, define the subarray $ S_j = \\{a_i \\mid l_j \\le i \\le r_j\\} $.  \nLet $ 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 $.  \nFind any integer $ x \\in \\mathbb{Z}^+ $ such that $ f_j(x) = 1 $, or output $ 0 $ if no such $ x $ exists.","simple_statement":null,"has_page_source":false}