F. One Occurrencetime limit per test3 secondsmemory limit per test768 megabytesinputstandard inputoutputstandard outputYou 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?InputThe 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).OutputAnswer 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.ExampleInput61 1 2 3 2 422 61 2Output40
Input61 1 2 3 2 422 61 2
Output40
['data structures', 'divide and conquer', '*2400']