#include <bits/stdc++.h>
using namespace std;
long long arr[100010], segarr[100010], mones[4000010], pones[4000010],
    sones[4000010], ln[4000010], lft[4000010], rgt[4000010], cnt = 0;
long long head[100050], ans[100050];
void copy(int i, int j) {
  mones[i] = mones[j];
  pones[i] = pones[j];
  sones[i] = sones[j];
  ln[i] = ln[j];
  lft[i] = lft[j];
  rgt[i] = rgt[j];
}
int build(int lb, int rb, int pos) {
  if (lb == rb) {
    ln[pos] = 1;
    return pos;
  }
  lft[pos] = build(lb, lb + (rb - lb) / 2, cnt++);
  rgt[pos] = build(1 + lb + (rb - lb) / 2, rb, cnt++);
  ln[pos] = ln[rgt[pos]] + ln[lft[pos]];
  return pos;
}
int inser(int cpnode, int lb, int rb, int vpos, int pos) {
  if (lb == rb) {
    mones[pos] = 1;
    pones[pos] = 1;
    sones[pos] = 1;
    ln[pos] = 1;
    return pos;
  }
  copy(pos, cpnode);
  if (vpos > lb + (rb - lb) / 2) {
    rgt[pos] = inser(rgt[pos], lb + (rb - lb) / 2 + 1, rb, vpos, cnt++);
  } else {
    lft[pos] = inser(lft[pos], lb, (rb - lb) / 2 + lb, vpos, cnt++);
  }
  mones[pos] = max(max(mones[lft[pos]], mones[rgt[pos]]),
                   sones[lft[pos]] + pones[rgt[pos]]);
  sones[pos] =
      ((sones[rgt[pos]] == ln[rgt[pos]]) ? ln[rgt[pos]] + sones[lft[pos]]
                                         : sones[rgt[pos]]);
  pones[pos] =
      ((pones[lft[pos]] == ln[lft[pos]]) ? ln[lft[pos]] + pones[rgt[pos]]
                                         : pones[lft[pos]]);
  return pos;
}
int n;
pair<pair<int, int>, pair<int, int> > qry(int l, int r, int pos, int lb = 1,
                                          int rb = n) {
  if (lb > r || rb < l)
    return pair<pair<int, int>, pair<int, int> >(pair<int, int>(0, 0),
                                                 pair<int, int>(0, 0));
  if (rb <= r && lb >= l)
    return pair<pair<int, int>, pair<int, int> >(
        pair<int, int>(mones[pos], sones[pos]),
        pair<int, int>(pones[pos], ln[pos]));
  else if (lb == rb)
    return pair<pair<int, int>, pair<int, int> >(pair<int, int>(0, 0),
                                                 pair<int, int>(0, 0));
  pair<pair<int, int>, pair<int, int> > L =
      qry(l, r, lft[pos], lb, lb + (rb - lb) / 2);
  pair<pair<int, int>, pair<int, int> > R =
      qry(l, r, rgt[pos], 1 + lb + (rb - lb) / 2, rb);
  return pair<pair<int, int>, pair<int, int> >(
      pair<int, int>(max(max(L.first.first, R.first.first),
                         L.first.second + R.second.first),
                     R.first.second == R.second.second
                         ? R.first.second + L.first.second
                         : R.first.second),
      pair<int, int>(L.second.first == L.second.second
                         ? R.second.first + L.second.first
                         : L.second.first,
                     L.second.second + R.second.second));
}
void bs(int l, int r, vector<pair<pair<int, int>, pair<int, int> > > v) {
  if (v.empty()) return;
  vector<pair<pair<int, int>, pair<int, int> > > v1, v2;
  for (auto k : v) ans[k.second.second] = arr[l];
  if (l == r) return;
  for (auto k : v) {
    if (qry(k.first.first, k.first.second, head[(l + r) / 2]).first.first >=
        k.second.first) {
      v1.push_back(k);
    } else
      v2.push_back(k);
  }
  bs(l, (r + l) >> 1, v2);
  bs(1 + ((r + l) >> 1), r, v1);
}
int main() {
  memset(lft, -1, sizeof lft);
  memset(rgt, -1, sizeof rgt);
  cnt++;
  cin >> n;
  priority_queue<pair<int, int> > s;
  for (int i = 1, __ = n + 1; i < __; ++i) {
    cin >> arr[i];
    s.push(pair<int, int>(arr[i], i));
  }
  sort(arr + 1, arr + 1 + n);
  head[n] = build(1, n, 0);
  int rn = n;
  while (!s.empty()) {
    head[rn - 1] = inser(head[rn], 1, n, s.top().second, cnt++);
    s.pop();
    rn--;
  }
  int q;
  cin >> q;
  vector<pair<pair<int, int>, pair<int, int> > > v;
  for (int i = 0, __ = q; i < __; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    v.push_back(pair<pair<int, int>, pair<int, int> >(pair<int, int>(a, b),
                                                      pair<int, int>(c, i)));
  }
  bs(1, n, v);
  for (int i = 0, __ = q; i < __; ++i) cout << ans[i] << endl;
  return 0;
}
