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?

Input

The first line contains one integer n (1 ≤ n ≤ 5 ⋅ 10^5).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 5 ⋅ 10^5).

The third line contains one integer q (1 ≤ q ≤ 5 ⋅ 10^5).

Then q lines follow, i-th line containing two integers l_i and r_i representing i-th query (1 ≤ l_i ≤ r_i ≤ 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.

Example

Input

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

Output

4 0

inputFormat

Input

The first line contains one integer n (1 ≤ n ≤ 5 ⋅ 10^5).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 5 ⋅ 10^5).

The third line contains one integer q (1 ≤ q ≤ 5 ⋅ 10^5).

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

outputFormat

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.

Example

Input

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

Output

4 0

样例

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

4
0

</p>