#include <bits/stdc++.h>
using namespace std;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(long long a) {
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(long long a) {
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  write(a);
  puts("");
}
const long long N = 500005, mod = 998244353;
pair<long long, long long> tree[N << 2], lazy[N << 2];
vector<long long> v[N];
vector<pair<pair<long long, long long>, pair<long long, long long> > > f[N];
long long a[N], n;
void cao(long long nod, pair<long long, long long> x) {
  tree[nod] = max(tree[nod], x);
  lazy[nod] = max(lazy[nod], x);
}
void pushdown(long long nod) {
  cao(nod << 1, lazy[nod]);
  cao(nod << 1 | 1, lazy[nod]);
  lazy[nod] = make_pair(0, 0);
}
void insert(long long l, long long r, long long i, long long j,
            pair<long long, long long> s, long long nod) {
  if (l == i && r == j) {
    cao(nod, s);
    return;
  }
  pushdown(nod);
  long long mid = (l + r) >> 1;
  if (j <= mid)
    insert(l, mid, i, j, s, nod << 1);
  else if (i > mid)
    insert(mid + 1, r, i, j, s, nod << 1 | 1);
  else {
    insert(l, mid, i, mid, s, nod << 1);
    insert(mid + 1, r, mid + 1, j, s, nod << 1 | 1);
  }
  tree[nod] = max(tree[nod << 1], tree[nod << 1 | 1]);
}
pair<long long, long long> ask(long long l, long long r, long long x,
                               long long nod) {
  if (l == r) return tree[nod];
  pushdown(nod);
  long long mid = (l + r) >> 1;
  if (x <= mid)
    return ask(l, mid, x, nod << 1);
  else
    return ask(mid + 1, r, x, nod << 1 | 1);
}
long long q, l[N], r[N];
map<long long, long long> M[N];
signed main() {
  n = read();
  for (long long i = 1; i <= 500000; i++) v[i].push_back(0);
  for (long long i = 1; i <= n; i++) v[read()].push_back(i);
  for (long long i = 1; i <= 500000; i++) v[i].push_back(n + 1);
  for (long long i = 1; i <= 500000; i++)
    for (unsigned j = 1; j + 1 < v[i].size(); j++) {
      f[v[i][j - 1] + 1].push_back(make_pair(
          make_pair(v[i][j] + 1, i), make_pair(v[i][j], v[i][j + 1] - 1)));
    }
  q = read();
  for (long long i = 1; i <= q; i++) {
    l[i] = read();
    r[i] = read();
    M[l[i]][r[i]] = 0;
  }
  for (long long i = 1; i <= n; i++) {
    for (unsigned j = 0; j < f[i].size(); j++)
      insert(1, n, f[i][j].second.first, f[i][j].second.second, f[i][j].first,
             1);
    for (map<long long, long long>::iterator it = M[i].begin();
         it != M[i].end(); it++) {
      pair<long long, long long> t = ask(1, n, it->first, 1);
      if (t.first > i) it->second = t.second;
    }
  }
  for (long long i = 1; i <= q; i++) writeln(M[l[i]][r[i]]);
}
