#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';
}
/*#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 (l < ql) remove(l++);
    *it = vis.calc(qb);
  }
  for (int i : ans) std::cout << i << '\n';
}*/

answer.code:6:7: error: expected nested-name-specifier before ‘ull’
    6 | using ull = unsigned long long;
      |       ^~~
answer.code:12:8: error: ‘array’ in namespace ‘std’ does not name a template type
   12 |   std::array<ull, (N - 1) / B + 2> a;
      |        ^~~~~
answer.code:12:3: note: ‘std::array’ is only available from C++11 onwards
   12 |   std::array<ull, (N - 1) / B + 2> a;
      |   ^~~
answer.code:16:3: error: ‘ull’ does not name a type
   16 |   ull gets(int i) {
      |   ^~~
answer.code: In constructor ‘bitset<N>::bitset()’:
answer.code:13:14: error: class ‘bitset<N>’ does not have any field named ‘a’
   13 |   bitset() : a() {}
      |              ^
answer.code: In member function ‘void bitset<N>::set(int)’:
answer.code:14:21: error: ‘a’ was not declared in this scope
   14 |   void set(int i) { a[i >> 6] |= 1ull << (i & 63); }
      |                     ^
answer.code: In member function ‘void bitset<N>::reset(int)’:
answer.code:15:23: error: ‘a’ was not declared in this scope
   15 |   void reset(int i) { a[i >> 6] &= ~(1ull << (i & 63)); }
      |                       ^
answer.code: In member function ‘int bitset<N>::calc(int)’:
answer.code:24:7: error: ‘ull’ was not declared in this scope
   24 |       ull cur = -1;
      |       ^~~
answer.code:25:22: error: ‘cur’ was not declared in this scope
   25 |       if (k - i < B) cur &= (1ull << (k - i)) - 1;
      |                      ^~~
answer.code:26:30: error: ‘cur’ was not declared in this scope
   26 |       for (int j = i, c = 1; cur &= gets(j); j += k, c++) chkmax(ret, c);
      |                              ^~~
answer.code:26:41: warning: ‘char* gets(char*)’ is deprecated [-Wdeprecated-declarations]
   26 |       for (int j = i, c = 1; cur &= gets(j); j += k, c++) chkmax(ret, c);
      |                                     ~~~~^~~
In file included from /usr/include/stdio.h:867,
                 from /usr/include/c++/13/cstdio:42,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:119,
                 from answer.code:1:
/usr/include/x86_64-linux-gnu/bits/stdio2.h:235:1: note: declared here
  235 | gets (char *__str)
      | ^~~~
answer.code:26:41: warning: ‘char* gets(char*)’ is deprecated [-Wdeprecated-declarations]
   26 |       for (int j = i, c = 1; cur &= gets(j); j += k, c++) chkmax(ret, c);
      |                                     ~~~~^~~
/usr/include/x86_64-linux-gnu/bits/stdio2.h:235:1: note: declared here
  235 | gets (char *__str)
      | ^~~~
answer.code: In function ‘int main()’:
answer.code:38:14: error: ISO C++ forbids declaration of ‘x’ with no type [-fpermissive]
   38 |   for (auto &x : a) std::cin >> x;
      |              ^
answer.code:38:18: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’ [-Wc++11-extensions]
   38 |   for (auto &x : a) std::cin >> x;
      |                  ^
answer.code:38:18: error: forming reference to reference type ‘std::vector<int>&’
answer.code:41:20: error: ‘tuple’ is not a member of ‘std’
   41 |   std::vector<std::tuple<int, int, int, int *>> q(m);
      |                    ^~~~~
answer.code:41:20: note: ‘std::tuple’ is only available from C++11 onwards
answer.code:41:20: error: ‘tuple’ is not a member of ‘std’
answer.code:41:20: note: ‘std::tuple’ is only available from C++11 onwards
answer.code:41:52: error: template argument 1 is invalid
   41 |   std::vector<std::tuple<int, int, int, int *>> q(m);
      |                                                    ^
answer.code:41:52: error: template argument 2 is invalid
answer.code:42:19: warning: range-based ‘for’ loops with initializer only available with ‘-std=c++20’ or ‘-std=gnu++20’ [-Wc++20-extensions]
   42 |   for (int i = 0; auto &[l, r, b, it] : q) {
      |                   ^~~~
answer.code:42:24: error: expected ‘[’ before ‘&’ token
   42 |   for (int i = 0; auto &[l, r, b, it] : q) {
      |                        ^
      |                        [
answer.code:42:24: error: expected identifier before ‘&’ token
answer.code:42:23: error: expected ‘]’ before ‘&’ token
   42 |   for (int i = 0; auto &[l, r, b, it] : q) {
      |                       ^~
      |                       ]
answer.code:45:4: error: expected ‘;’ before ‘std’
   45 |   }
      |    ^
      |    ;
   46 |   std::sort(q.begin(), q.end(), [](auto x, auto y) -> bool {
      |   ~~~
answer.code:46:13: error: ‘q’ was not declared in this scope
   46 |   std::sort(q.begin(), q.end(), [](auto x, auto y) -> bool {
      |             ^
answer.code:46:41: error: ‘x’ does not name a type
   46 |   std::sort(q.begin(), q.end(), [](auto x, auto y) -> bool {
      |                                         ^
answer.code: In lambda function:
answer.code:51:5: error: expected ‘{’ before ‘;’ token
   51 |   });
      |     ^
answer.code: In function ‘int main()’:
answer.code:51:5: warning: lambda expressions only available with ‘-std=c++11’ or ‘-std=gnu++11’ [-Wc++11-extensions]
answer.code:51:...