Bizon the Champion has recently finished painting his wood fence. The fence consists of a sequence of n panels of 1 meter width and of arbitrary height. The i-th panel's height is hi meters. The adjacent planks follow without a gap between them.

After Bizon painted the fence he decided to put a "for sale" sign on it. The sign will be drawn on a rectangular piece of paper and placed on the fence so that the sides of the sign are parallel to the fence panels and are also aligned with the edges of some panels. Bizon the Champion introduced the following constraints for the sign position:

  1. The width of the sign should be exactly w meters. 
  2. The sign must fit into the segment of the fence from the l-th to the r-th panels, inclusive (also, it can't exceed the fence's bound in vertical direction). 



The sign will be really pretty, So Bizon the Champion wants the sign's height to be as large as possible.

You are given the description of the fence and several queries for placing sign. For each query print the maximum possible height of the sign that can be placed on the corresponding segment of the fence with the given fixed width of the sign.

Input

The first line of the input contains integer n — the number of panels in the fence (1 ≤ n ≤ 105). 

The second line contains n space-separated integers hi, — the heights of the panels (1 ≤ hi ≤ 109). 

The third line contains an integer m — the number of the queries (1 ≤ m ≤ 105). 

The next m lines contain the descriptions of the queries, each query is represented by three integers l, r and w (1 ≤ l ≤ r ≤ n, 1 ≤ w ≤ r - l + 1) — the segment of the fence and the width of the sign respectively.

Output

For each query print the answer on a separate line — the maximum height of the sign that can be put in the corresponding segment of the fence with all the conditions being satisfied.

Examples

Input

5
1 2 2 3 3
3
2 5 3
2 5 2
1 5 5


Output

2
3
1

Note

The fence described in the sample looks as follows: 

<image>

The possible positions for the signs for all queries are given below.

<image> The optimal position of the sign for the first query.  <image> The optimal position of the sign for the second query.  <image> The optimal position of the sign for the third query. 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
template <typename valueType, typename modType>
struct SegmentTreeNode {
 public:
  std::size_t id;
  long long left, right;
  valueType val;
  modType mod;
};
template <typename valueType, typename modType,
          bool elementModificationOnly = false>
class SegmentTree {
 public:
  SegmentTree() = default;
  SegmentTree(
      const std::vector<valueType> &_initValue,
      std::function<valueType(const valueType &, const valueType &)> _merge,
      std::function<void(SegmentTreeNode<valueType, modType> &,
                         const modType &)>
          _update,
      long long _startPoint = 1, const valueType &_valueZero = valueType(),
      const modType &_modZero = modType()) {
    init(_initValue, _merge, _update, _startPoint, _valueZero, _modZero);
  }
  void init(
      const std::vector<valueType> &_initValue,
      std::function<valueType(const valueType &, const valueType &)> _merge,
      std::function<void(SegmentTreeNode<valueType, modType> &,
                         const modType &)>
          _update,
      long long _startPoint = 1, const valueType &_valueZero = valueType(),
      const modType &_modZero = modType()) {
    assert(_startPoint >= LLONG_MIN / 2);
    assert(_startPoint <= LLONG_MAX / 2 - (long long)_initValue.size());
    leftRange = _startPoint;
    rightRange = _startPoint + _initValue.size();
    m_init(_initValue, _merge, _update, _valueZero, _modZero);
  }
  void modify(long long l, long long r, const modType &mod) {
    assert(!elementModificationOnly);
    modify(1, leftRange, rightRange, l, r, mod);
  }
  void modify(long long p, const modType &mod) {
    assert(p < LLONG_MAX);
    modify(1, leftRange, rightRange, p, p + 1, mod);
  }
  valueType query(long long l, long long r) {
    return query(1, leftRange, rightRange, l, r);
  }
  valueType query(long long p) { return query(p, p + 1); }

 private:
  void pushup(std::size_t cur) {
    nodes[cur].val = merge(nodes[cur << 1].val, nodes[cur << 1 | 1].val);
  }
  void pushdown(std::size_t cur) {
    update(nodes[cur << 1], nodes[cur].mod);
    update(nodes[cur << 1 | 1], nodes[cur].mod);
    nodes[cur].mod = modZero;
  }
  void build(std::size_t cur, long long l, long long r,
             const std::vector<valueType> &initValue) {
    nodes[cur].id = cur;
    nodes[cur].left = l;
    nodes[cur].right = r;
    nodes[cur].mod = modZero;
    if (l == r - 1)
      nodes[cur].val = initValue[l - leftRange];
    else {
      build(cur << 1, l, (l + r) >> 1, initValue);
      build(cur << 1 | 1, (l + r) >> 1, r, initValue);
      pushup(cur);
    }
  }
  void m_init(
      const std::vector<valueType> &_initValue,
      std::function<valueType(const valueType &, const valueType &)> _merge,
      std::function<void(SegmentTreeNode<valueType, modType> &,
                         const modType &)>
          _update,
      const valueType &_valueZero, const modType &_modZero) {
    merge = _merge;
    update = _update;
    valueZero = _valueZero;
    modZero = _modZero;
    nodes.resize((rightRange - leftRange) << 2);
    build(1, leftRange, rightRange, _initValue);
  }
  void modify(std::size_t cur, long long l, long long r, long long L,
              long long R, const modType &mod) {
    if (l >= R || r <= L) return;
    if (L <= l && r <= R)
      update(nodes[cur], mod);
    else {
      if (!elementModificationOnly) pushdown(cur);
      modify(cur << 1, l, (l + r) >> 1, L, R, mod);
      modify(cur << 1 | 1, (l + r) >> 1, r, L, R, mod);
      pushup(cur);
    }
  }
  valueType query(std::size_t cur, long long l, long long r, long long L,
                  long long R) {
    if (l >= R || r <= L) return valueZero;
    if (L <= l && r <= R) return nodes[cur].val;
    if (!elementModificationOnly) pushdown(cur);
    return merge(query(cur << 1, l, (l + r) >> 1, L, R),
                 query(cur << 1 | 1, (l + r) >> 1, r, L, R));
  }
  std::function<valueType(const valueType &, const valueType &)> merge;
  std::function<void(SegmentTreeNode<valueType, modType> &, const modType &)>
      update;
  std::vector<SegmentTreeNode<valueType, modType>> nodes;
  long long leftRange = 0, rightRange = 0;
  valueType valueZero;
  modType modZero;
};
using namespace std;
const long double inf = 1e121;
const long double eps = 1e-10;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randint(int l, int r) {
  int out = rng() % (r - l + 1) + l;
  return out >= l ? out : out + r - l + 1;
}
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ",";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ",";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + "," + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + "," + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + "," + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + "," + to_string(get<3>(p)) + ")";
}
template <typename A, typename B, typename C, typename D, typename E>
string to_string(tuple<A, B, C, D, E> p) {
  return "(" + to_string(get<0>(p)) + "," + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + "," + to_string(get<3>(p)) + "," +
         to_string(get<4>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
template <typename T>
struct is_pair {
  static const bool value = false;
};
template <typename T, typename U>
struct is_pair<std::pair<T, U>> {
  static const bool value = true;
};
const int INF = 0x3f3f3f3f;
template <typename T>
typename enable_if<!is_integral<T>::value && !is_pair<T>::value, void>::type
read(T &x) {
  cin >> x;
}
long long read() {
  char c;
  long long out = 0, f = 1;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
    ;
  if (c == '-') {
    f = -1;
    c = getchar();
  }
  for (; isdigit(c); c = getchar()) out = (out << 3) + (out << 1) + c - '0';
  return out * f;
}
template <typename T>
typename enable_if<is_integral<T>::value, T>::type read(T &x) {
  char c;
  T f = 1;
  x = 0;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
    ;
  if (c == '-') {
    f = -1;
    c = getchar();
  }
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
  return x *= f;
}
char read(char &x) {
  for (x = getchar(); isspace(x); x = getchar())
    ;
  return x;
}
double read(double &x) {
  scanf("%lf", &x);
  return x;
}
long double read(long double &x) {
  scanf("%Lf", &x);
  return x;
}
template <typename T>
typename enable_if<!is_integral<T>::value && !is_pair<T>::value, void>::type
write(const T &x) {
  cout << x;
}
template <typename T>
typename enable_if<is_integral<T>::value, void>::type write(const T &x) {
  if (x < 0) {
    putchar('-');
    write(-x);
    return;
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
void write(const char &x) { putchar(x); }
void write(const double &x) { printf("%.10lf", x); }
void write(const long double &x) { printf("%.10Lf", x); }
template <typename T>
typename enable_if<is_pair<T>::value, void>::type read(T &x) {
  read(x.first);
  read(x.second);
}
template <typename T>
typename enable_if<is_pair<T>::value, void>::type write(const T &x) {
  write(x.first);
  putchar(' ');
  write(x.second);
}
template <typename T, typename... Args>
void read(T &x, Args &...args) {
  read(x);
  read(args...);
}
template <
    typename OutputIt,
    typename = typename enable_if<
        is_same<output_iterator_tag,
                typename iterator_traits<OutputIt>::iterator_category>::value ||
        (is_base_of<forward_iterator_tag, typename iterator_traits<OutputIt>::
                                              iterator_category>::value &&
         !is_const<OutputIt>::value)>::type>
void read(OutputIt __first, OutputIt __last) {
  for (; __first != __last; ++__first) read(*__first);
}
template <
    typename InputIt,
    typename = typename enable_if<is_base_of<
        input_iterator_tag,
        typename iterator_traits<InputIt>::iterator_category>::value>::type>
void wts(InputIt __first, InputIt __last) {
  bool isFirst = true;
  for (; __first != __last; ++__first) {
    if (isFirst)
      isFirst = false;
    else
      putchar(' ');
    write(*__first);
  }
  putchar('\n');
}
template <
    typename InputIt,
    typename = typename enable_if<is_base_of<
        input_iterator_tag,
        typename iterator_traits<InputIt>::iterator_category>::value>::type>
void wtb(InputIt __first, InputIt __last) {
  for (; __first != __last; ++__first) {
    write(*__first);
    putchar('\n');
  }
}
template <typename T>
void wts(const T &x) {
  write(x);
  putchar(' ');
}
template <typename T>
void wtb(const T &x) {
  write(x);
  putchar('\n');
}
template <typename T>
void wte(const T &x) {
  write(x);
  exit(0);
}
template <typename T, typename... Args>
void wts(const T &x, Args... args) {
  wts(x);
  wts(args...);
}
template <typename T, typename... Args>
void wtb(const T &x, Args... args) {
  wts(x);
  wtb(args...);
}
template <typename T, typename... Args>
void wte(const T &x, Args... args) {
  wts(x);
  wte(args...);
}
template <typename T1, typename T2>
inline bool up(T1 &x, const T2 &y) {
  return x < y ? x = y, 1 : 0;
}
template <typename T1, typename T2>
inline bool dn(T1 &x, const T2 &y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T1, typename T2, typename T3>
inline bool inRange(const T1 &x, const T2 &l, const T3 &r) {
  return !(x < l) && !(r < x);
}
template <typename T1, typename T2>
inline auto minOfDifferentTypes(const T1 &x, const T2 &y)
    -> decltype(x < y ? x : y) {
  return x < y ? x : y;
}
template <typename T1, typename T2>
inline auto maxOfDifferentTypes(const T1 &x, const T2 &y)
    -> decltype(x < y ? y : x) {
  return x < y ? y : x;
}
template <typename T1, typename T2, typename T3>
inline T1 &madd(T1 &x, const T2 &y, const T3 &modulo) {
  return x = (long long)(x + y + modulo) % modulo;
}
template <typename T1, typename T2, typename T3>
inline T1 &mmul(T1 &x, const T2 &y, const T3 &modulo) {
  return x = (long long)x * y % modulo;
}
inline int modadd(int x, int y, int modulo) {
  return (x += y) >= modulo ? x - modulo : x;
}
inline int isinf(int x) { return x < INF ? x : -1; }
inline void yesno(bool x) { wtb(x ? "Yes" : "No"); }
struct Modify {
  int p, x;
};
struct Query {
  int l, r, w, id;
};
struct Val {
  int ans, pre, suf, sum;
};
signed main() {
  int n = read();
  vector<Modify> modify;
  vector<int> lsh;
  for (int i = (1), iend = (n); i <= iend; ++i) {
    int x = read();
    lsh.push_back(x);
    modify.push_back({i, x});
  }
  sort((lsh).begin(), (lsh).end());
  lsh.resize(unique((lsh).begin(), (lsh).end()) - lsh.begin());
  for (auto &m : modify)
    m.x = lower_bound((lsh).begin(), (lsh).end(), m.x) - lsh.begin();
  int k = read();
  vector<Query> query;
  for (int i = (0), iend = (k - 1); i <= iend; ++i) {
    int l = read();
    int r = read();
    int w = read();
    query.push_back({l, r, w, i});
  }
  SegmentTree<Val, int, true> seg(
      vector<Val>(n, {0, 0, 0, -n}),
      [n](const Val &x, const Val &y) {
        Val res;
        res.ans = maxOfDifferentTypes(x.suf + y.pre,
                                      maxOfDifferentTypes(x.ans, y.ans));
        res.pre = maxOfDifferentTypes(x.pre, x.sum + y.pre);
        res.suf = maxOfDifferentTypes(y.suf, x.suf + y.sum);
        res.sum = maxOfDifferentTypes(x.sum + y.sum, -n);
        return res;
      },
      [](SegmentTreeNode<Val, int> &node, int x) {
        if (x == INF) return;
        node.val.ans = node.val.pre = node.val.suf = maxOfDifferentTypes(0, x);
        node.val.sum = x;
      },
      1, {0, 0, 0, 0}, INF);
  vector<int> ans(k);
  function<void(vector<Modify> &, vector<Query> &, int, int)> solve =
      [&](vector<Modify> &ms, vector<Query> &qs, int l, int r) {
        if (qs.empty()) return;
        if (l == r - 1) {
          for (auto q : qs) {
            ans[q.id] = lsh[l];
          }
          return;
        }
        vector<Modify> lm, rm;
        int mid = (l + r) >> 1;
        for (auto m : ms) {
          if (m.x >= mid) {
            seg.modify(m.p, 1);
            rm.push_back(m);
          } else
            lm.push_back(m);
        }
        vector<Query> lq, rq;
        for (auto q : qs) {
          if (seg.query(q.l, q.r + 1).ans >= q.w)
            rq.push_back(q);
          else
            lq.push_back(q);
        }
        vector<Modify>().swap(ms);
        vector<Query>().swap(qs);
        solve(lm, lq, l, mid);
        for (auto m : rm) seg.modify(m.p, -n);
        solve(rm, rq, mid, r);
      };
  solve(modify, query, 0, lsh.size());
  for (auto x : ans) wtb(x);
  return 0;
}
