#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, d = 1;
  char y = getchar();
  while (y < '0' || y > '9') {
    if (y == '-') d = -1;
    y = getchar();
  }
  while (y >= '0' && y <= '9') {
    x = (x << 3) + (x << 1) + (y ^ '0');
    y = getchar();
  }
  return x * d;
}
const int N = 1e5 + 10, M = 8e6 + 10;
struct node {
  int k, id;
} a[N];
struct que {
  int xl, xr, k;
} b[N];
bool cmp1(node x, node y) { return x.k < y.k; }
bool cmp2(que x, que y) { return x.k < y.k; }
int n, m, mx = 0, cnt = 0, c[N], d[N], root[N], zh[M][2], zmx[M], lmx[M],
          rmx[M];
void push_up(int l, int r, int t) {
  int ls = zh[t][0], rs = zh[t][1], mid = (l + r) >> 1;
  zmx[t] = max(max(zmx[ls], zmx[rs]), rmx[ls] + lmx[rs]);
  lmx[t] = (lmx[ls] == mid - l + 1 ? lmx[ls] + lmx[rs] : lmx[ls]);
  rmx[t] = (rmx[rs] == r - mid ? rmx[rs] + rmx[ls] : rmx[rs]);
}
void build(int l, int r, int &t) {
  t = ++cnt;
  if (l == r) {
    lmx[t] = rmx[t] = zmx[t] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, zh[t][0]);
  build(mid + 1, r, zh[t][1]);
  push_up(l, r, t);
}
void modify(int l, int r, int &t1, int t2, int x) {
  if (!t1) t1 = ++cnt;
  if (l == r) {
    lmx[t1] = rmx[t1] = zmx[t1] = 0;
    return;
  }
  int mid = (l + r) >> 1;
  if (mid >= x)
    zh[t1][1] = zh[t2][1], modify(l, mid, zh[t1][0], zh[t2][0], x);
  else
    zh[t1][0] = zh[t2][0], modify(mid + 1, r, zh[t1][1], zh[t2][1], x);
  push_up(l, r, t1);
}
int md1, md2;
void query(int l, int r, int t, int pl, int pr) {
  if (!t) {
    md2 = 0;
    return;
  }
  if (l >= pl && r <= pr) {
    md1 = max(max(md1, zmx[t]), md2 + lmx[t]);
    md2 = (rmx[t] == r - l + 1 ? rmx[t] + md2 : rmx[t]);
    return;
  }
  int mid = (l + r) >> 1;
  if (mid >= pl) query(l, mid, zh[t][0], pl, pr);
  if (mid < pr) query(mid + 1, r, zh[t][1], pl, pr);
}
bool check(int t, int y) {
  md1 = md2 = 0;
  query(1, n, root[y], b[t].xl, b[t].xr);
  return md1 >= b[t].k;
}
int main() {
  n = read();
  for (register int i = 1; i <= n; i++) a[i].k = read(), a[i].id = i;
  m = read();
  for (register int i = 1; i <= m; i++) {
    b[i].xl = read();
    b[i].xr = read();
    b[i].k = read();
  }
  sort(a + 1, a + n + 1, cmp1);
  for (register int i = 1; i <= n; i++) {
    d[++mx] = a[i].k;
    while (i < n && a[i].k == a[i + 1].k) c[a[i++].id] = mx;
    c[a[i].id] = mx;
  }
  build(1, n, root[0]);
  for (register int i = 1, j = 1, t; i <= mx; i++) {
    root[i] = root[i - 1];
    while (j <= n) {
      while (j <= n && a[j].id > n) ++j;
      if (j <= n && c[a[j].id] < i) {
        t = root[i];
        root[i] = 0;
        modify(1, n, root[i], t, a[j++].id);
      } else
        break;
    }
  }
  for (register int i = 1; i <= m; i++) {
    int l = 1, r = mx, mid;
    while (l < r) {
      mid = (l + r + 1) >> 1;
      if (check(i, mid))
        l = mid;
      else
        r = mid - 1;
    }
    printf("%d\n", d[l]);
  }
  return 0;
}
