#include <bits/stdc++.h>
template <class T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
using ull = unsigned long long;
const int N = 100100;

template <int N>
struct bitset {
  static const int B = 64;
  std::array<ull, (N - 1) / B + 2> a;
  bitset() : a() {}
  void set(int i) { a[i >> 6] |= 1ull << (i & 63); }
  void reset(int i) { a[i >> 6] &= ~(1ull << (i & 63)); }
  ull gets(int i) {
    if (i >= N) return 0;
    return a[i >> 6] >> (i & 63) |
           ((i & 63) ? a[(i >> 6) + 1] << (B - (i & 63)) : 0);
  }
  int calc(int k) {
    int ret = 0;
    for (int i = 0; i < k; i += B) {
      ull cur = -1;
      if (k - i < B) cur &= (1ull << (k - i)) - 1;
      for (int j = i, c = 1; cur &= gets(j); j += k, c++) chkmax(ret, c);
    }
    return ret;
  }
};

int main() {
  const int B = 10;
  std::cin.tie(0)->sync_with_stdio(0);
  int n, m;
  std::cin >> n;
  std::vector<int> a(n);
  for (auto &x : a) std::cin >> x;
  std::cin >> m;
  std::vector<int> ans(m);
  std::vector<std::tuple<int, int, int, int *>> q(m);
  for (int i = 0; auto &[l, r, b, it] : q) {
    std::cin >> l >> r >> b, l--, r--;
    it = &ans[i++];
  }
  std::sort(q.begin(), q.end(), [](auto x, auto y) -> bool {
    auto [l1, r1, b1, it1] = x;
    auto [l2, r2, b2, it2] = y;
    if (l1 / 400 == l2 / 400) return (r1 < r2) ^ ((l1 / 400) & 1);
    return l1 < l2;
  });
  for (int b = 1; b < B; b++) {
    std::vector<std::array<int, N>> cnt(b);
    std::vector<std::bitset<N>> vis(b);
    for (auto &t : vis) t.set();
    auto add = [&](int i) {
      if (!cnt[a[i] % b][a[i] / b]++) vis[a[i] % b][a[i] / b] = 0;
    };
    auto remove = [&](int i) {
      if (!--cnt[a[i] % b][a[i] / b]) vis[a[i] % b][a[i] / b] = 1;
    };
    int l = 1, r = 0;
    for (auto [ql, qr, qb, it] : q) {
      if (qb != b) continue;
      while (r < qr) add(++r);
      while (l > ql) add(--l);
      while (r > qr) remove(r--);
      while (l < ql) remove(l++);
      for (int i = 0; i < b; i++) {
        chkmax<int>(*it, vis[i]._Find_first());
      }
    }
  }
  std::array<int, N> cnt{};
  bitset<N> vis;
  auto add = [&](int i) {
    if (!cnt[a[i]]++) vis.set(a[i]);
  };
  auto remove = [&](int i) {
    if (!--cnt[a[i]]) vis.reset(a[i]);
  };
  int l = 1, r = 0;
  for (auto [ql, qr, qb, it] : q) {
    if (qb < B) continue;
    while (r < qr) add(++r);
    while (l > ql) add(--l);
    while (r > qr) remove(r--);
    while (l < ql) remove(l++);
    *it = vis.calc(qb);
  }
  for (int i : ans) std::cout << i << '\n';
}