#include <bits/stdc++.h>
using namespace std;
int a, b, c, d, e, i, j, ii, jj, zx, xc, tes, t, f[100009], lef[100009],
    rig[100009], mid[100009], pi, bi, seg[400009], seglf[400009], segrg[400009],
    za, sl[400009], le[400009], ri[400009], l, r, sg, sglf, sgrg, Sl;
pair<int, int> p[100009], q[100009];
pair<pair<int, int>, int> pp[100009];
void upd(int rr) {
  if (rr == 0) return;
  seglf[rr] = max(seglf[rr * 2], sl[rr * 2] + seglf[rr * 2 + 1]);
  segrg[rr] = max(segrg[rr * 2 + 1], sl[rr * 2 + 1] + segrg[rr * 2]);
  seg[rr] =
      max(max(seg[rr * 2], seg[rr * 2 + 1]), segrg[rr * 2] + seglf[rr * 2 + 1]);
  if (sl[rr * 2] > 0 && sl[rr * 2 + 1] > 0) {
    sl[rr] = sl[rr * 2] + sl[rr * 2 + 1];
  } else {
    sl[rr] = -999999;
  }
  upd(rr / 2);
}
void read(int q, int w, int rr) {
  if (q > r || w < l) return;
  if (q >= l && w <= r) {
    sglf = max(seglf[0], sl[0] + seglf[rr]);
    sgrg = max(segrg[rr], sl[rr] + segrg[0]);
    sg = max(max(seg[rr], seg[0]), segrg[0] + seglf[rr]);
    if (sl[0] > 0 && sl[rr] > 0) {
      Sl = sl[0] + sl[rr];
    } else {
      Sl = -999999;
    }
    seg[0] = sg;
    seglf[0] = sglf;
    segrg[0] = sgrg;
    sl[0] = Sl;
    return;
  }
  read(q, (q + w) / 2, rr * 2);
  read((q + w) / 2 + 1, w, rr * 2 + 1);
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> a;
  for (i = 1; i <= a; i++) cin >> f[i];
  for (i = 1; i <= a; i++) {
    q[i].first = f[i];
    q[i].second = i;
  }
  sort(q + 1, q + a + 1);
  za = 1;
  while (za < a) za *= 2;
  cin >> tes;
  for (t = 1; t <= tes; t++) {
    cin >> pp[t].first.first >> pp[t].first.second >> pp[t].second;
    lef[t] = 0;
    rig[t] = 1000000001;
  }
  while (1) {
    pi = 0;
    for (t = 1; t <= tes; t++) {
      if (lef[t] + 1 >= rig[t]) {
      } else {
        mid[t] = (lef[t] + rig[t]) / 2;
        pi++;
        p[pi].first = mid[t];
        p[pi].second = t;
      }
    }
    if (pi == 0) break;
    sort(p + 1, p + pi + 1);
    for (i = 0; i <= za * 2; i++) {
      seg[i] = 0;
      seglf[i] = segrg[i] = 0;
      sl[i] = -999999;
    }
    e = a;
    for (i = pi; i >= 1; i--) {
      c = p[i].second;
      while (e >= 1 && q[e].first >= p[i].first) {
        d = za + q[e].second - 1;
        seg[d] = 1;
        seglf[d] = segrg[d] = 1;
        sl[d] = 1;
        upd(d / 2);
        e--;
      }
      l = pp[c].first.first;
      r = pp[c].first.second;
      seg[0] = 0;
      seglf[0] = 0;
      segrg[0] = 0;
      sl[0] = 0;
      read(1, za, 1);
      if (seg[0] >= pp[c].second) {
        lef[c] = mid[c];
      } else {
        rig[c] = mid[c];
      }
    }
  }
  for (t = 1; t <= tes; t++) {
    cout << lef[t] << endl;
  }
  return 0;
}
