#include <bits/stdc++.h>
using namespace std;
using namespace std;
inline char nc() { return getchar(); }
inline void read(int &x) {
  char c = nc();
  int b = 1;
  for (; !(c >= '0' && c <= '9'); c = nc())
    if (c == '-') b = -1;
  for (x = 0; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = nc())
    ;
  x *= b;
}
inline void read(long long &x) {
  char c = nc();
  long long b = 1;
  for (; !(c >= '0' && c <= '9'); c = nc())
    if (c == '-') b = -1;
  for (x = 0; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = nc())
    ;
  x *= b;
}
inline void read(char &x) {
  for (x = nc(); !(x == '(' || x == ')'); x = nc())
    ;
}
inline int read(char *s) {
  char c = nc();
  int len = 1;
  for (; !(c == '(' || c == ')'); c = nc())
    if (c == EOF) return 0;
  for (; (c == '(' || c == ')'); s[len++] = c, c = nc())
    ;
  s[len++] = '\0';
  return len - 2;
}
int wt, ss[19];
inline void print(int x) {
  if (x < 0) x = -x, putchar('-');
  if (!x)
    putchar(48);
  else {
    for (wt = 0; x; ss[++wt] = x % 10, x /= 10)
      ;
    for (; wt; putchar(ss[wt] + 48), wt--)
      ;
  }
}
inline void print(long long x) {
  if (x < 0) x = -x, putchar('-');
  if (!x)
    putchar(48);
  else {
    for (wt = 0; x; ss[++wt] = x % 10, x /= 10)
      ;
    for (; wt; putchar(ss[wt] + 48), wt--)
      ;
  }
}
int T, n, m, s, k, h[100010], b[100010];
struct data {
  int x, id;
} d[100010];
struct ST {
  int lc, rc, ansl, ansr, ans;
} a[2000010];
int Hash(int x) { return lower_bound(b + 1, b + 1 + k, x) - b; }
void build(int l, int r, int x) {
  s++;
  x = s;
  a[x].ansl = 0, a[x].ansr = 0, a[x].ans = 0;
  if (l == r) {
    a[x].lc = a[x].rc = 0;
    return;
  }
  int mid = (l + r) >> 1;
  a[x].lc = s + 1;
  build(l, mid, x);
  a[x].rc = s + 1;
  build(mid + 1, r, x);
}
void change(int x, int y, int xx, int l, int r) {
  if (l == r) {
    a[x].ansl = 1;
    a[x].ansr = 1;
    a[x].ans = 1;
    return;
  }
  int mid = (l + r) >> 1;
  if (y <= mid) {
    a[x].rc = a[xx].rc;
    s++;
    a[x].lc = s;
    change(s, y, a[xx].lc, l, mid);
  } else {
    a[x].lc = a[xx].lc;
    s++;
    a[x].rc = s;
    change(s, y, a[xx].rc, mid + 1, r);
  }
  if (a[a[x].lc].ansl == mid - l + 1)
    a[x].ansl = mid - l + 1 + a[a[x].rc].ansl;
  else
    a[x].ansl = a[a[x].lc].ansl;
  if (a[a[x].rc].ansr == r - mid)
    a[x].ansr = r - mid + a[a[x].lc].ansr;
  else
    a[x].ansr = a[a[x].rc].ansr;
  a[x].ans = max(a[x].ansl, a[x].ansr);
  a[x].ans = max(a[x].ans, max(a[a[x].lc].ans, a[a[x].rc].ans));
  a[x].ans = max(a[x].ans, a[a[x].lc].ansr + a[a[x].rc].ansl);
}
ST query(int lq, int rq, int l, int r, int z) {
  if (lq <= l && rq >= r) return a[z];
  int mid = l + r >> 1;
  if (rq <= mid) return query(lq, rq, l, mid, a[z].lc);
  if (lq > mid) return query(lq, rq, mid + 1, r, a[z].rc);
  ST x = query(lq, rq, l, mid, a[z].lc);
  ST y = query(lq, rq, mid + 1, r, a[z].rc);
  ST ans;
  if (x.ansl == mid - l + 1)
    ans.ansl = mid - l + 1 + y.ansl;
  else
    ans.ansl = x.ansl;
  if (y.ansr == r - mid)
    ans.ansr = r - mid + x.ansr;
  else
    ans.ansr = y.ansr;
  ans.ans = max(ans.ansl, ans.ansr);
  ans.ans = max(ans.ans, max(x.ans, y.ans));
  ans.ans = max(ans.ans, x.ansr + y.ansl);
  return ans;
}
bool cmp(data x, data y) { return x.x > y.x; }
int main() {
  read(n);
  memset(a, 0, sizeof(a));
  for (int i = 1; i <= n; i++) read(b[i]), d[i].x = b[i], d[i].id = i;
  sort(b + 1, b + 1 + n);
  k = unique(b + 1, b + 1 + n) - b - 1;
  s = 0;
  build(1, n, 1);
  h[0] = 1;
  sort(d + 1, d + 1 + n, cmp);
  int pre = 1;
  for (int i = 1; i <= n; i++) {
    s++;
    int x = s;
    change(s, d[i].id, pre, 1, n);
    h[Hash(d[i].x)] = x;
    pre = x;
  }
  scanf("%d", &m);
  int x, y, z;
  while (m--) {
    read(x);
    read(y);
    read(z);
    int l = 1, r = b[k], res, mid;
    while (l <= r) {
      int mid = l + r >> 1;
      ST tmp = query(x, y, 1, n, h[Hash(mid)]);
      if (tmp.ans >= z)
        res = mid, l = mid + 1;
      else
        r = mid - 1;
    }
    print(res), puts("");
  }
  return 0;
}
