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
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[500005], vis[500005], nx[500005];
struct nod {
  int r, id;
};
vector<nod> enq[500005];
int ans[500005];
int mx[2000005], pos[2000005];
void jia(int now, int l, int r, int ai, int v) {
  if (l == r) {
    mx[now] = v;
    pos[now] = l;
    return;
  }
  int mid = (l + r) >> 1;
  if (ai <= mid)
    jia((now << 1), l, mid, ai, v);
  else
    jia(((now << 1) | 1), mid + 1, r, ai, v);
  if (mx[(now << 1)] <= mx[((now << 1) | 1)]) {
    mx[now] = mx[((now << 1) | 1)];
    pos[now] = pos[((now << 1) | 1)];
  } else {
    mx[now] = mx[(now << 1)];
    pos[now] = pos[(now << 1)];
  }
}
nod query(int now, int l, int r, int st, int ed) {
  if (l >= st && r <= ed) {
    return (nod){mx[now], pos[now]};
  }
  int mid = (l + r) >> 1;
  nod x1, x2;
  x1.r = x2.r = 0;
  if (st <= mid) x1 = query((now << 1), l, mid, st, ed);
  if (ed >= mid + 1) x2 = query(((now << 1) | 1), mid + 1, r, st, ed);
  return x1.r > x2.r ? x1 : x2;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &m);
  for (int i = 1, x, y; i <= m; i++) {
    scanf("%d%d", &x, &y);
    enq[x].push_back((nod){y, i});
  }
  for (int i = n; i; i--) {
    nx[i] = vis[a[i]];
    if (nx[i] == 0) nx[i] = n + 1;
    vis[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    if (vis[a[i]] == i) jia(1, 1, n, i, nx[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < enq[i].size(); j++) {
      int r = enq[i][j].r;
      nod ans1 = query(1, 1, n, i, r);
      if (ans1.r > r)
        ans[enq[i][j].id] = a[ans1.id];
      else
        ans[enq[i][j].id] = 0;
    }
    if (nx[i] != n + 1) {
      jia(1, 1, n, nx[i], nx[nx[i]]);
    }
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}
