#include <iostream>
#include <algorithm>
#include <vector>

#define int long long

// Code for Mo's Algorithm based on CP-algorithms

const int block_size = 325;
const int MAXN = 100005;

int n;
int count[block_size];
int sum[block_size];
int num[MAXN];
int ct[MAXN];
int st[MAXN];
int a[MAXN];

void upd(int x, int v) {
  if(x == 0)
    return;

  ct[x] += v;
  st[x] += v*(x-1);
  count[x/block_size] += v;
  sum[x/block_size] += v*(x-1);
}

void remove(int idx) {
  upd(num[a[idx]], -1);
  num[a[idx]]--;
  upd(num[a[idx]], +1);
}

void add(int idx) {
  upd(num[a[idx]], -1);
  num[a[idx]]++;
  upd(num[a[idx]], +1);
}

int get_answer(int k) {
  int j = 0;
  int done = 0;

  while(j < block_size && sum[j] <= k) {
    k -= sum[j];
    done += count[j];
    j++;
  }

  if(j == block_size)
    return done;

  int id = j*block_size;
  while(st[id] <= k) {
    k -= st[id];
    done += ct[id];
    id++;
  }

  int add = k/(id-1);
  return done + add;
}

struct Query {
  int l, r, idx, k;
  bool operator<(Query other) const
  {
    return std::make_pair(l / block_size, r) <
      std::make_pair(other.l / block_size, other.r);
  }
};

std::vector<int> mo_s_algorithm(std::vector<Query> queries) {
  std::vector<int> answers(queries.size());
  std::sort(queries.begin(), queries.end());

  int cur_l = 0;
  int cur_r = -1;

  for (Query q : queries) {
    while (cur_l > q.l) {
      cur_l--;
      add(cur_l);
    }
    while (cur_r < q.r) {
      cur_r++;
      add(cur_r);
    }
    while (cur_l < q.l) {
      remove(cur_l);
      cur_l++;
    }
    while (cur_r > q.r) {
      remove(cur_r);
      cur_r--;
    }
    answers[q.idx] = get_answer(q.k);
  }
  return answers;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cin >> n;

  for(int i = 0; i < n; i++)
    std::cin >> a[i];

  std::vector<Query> qs;
  int q;
  std::cin >> q;

  for(int i = 0; i < q; i++) {
    int l, r, k;
    std::cin >> l >> r >> k;
    l--; r--;
    qs.push_back({l, r, i, k});
  }

  std::vector<int> ans = mo_s_algorithm(qs);

  for(int j : ans)
    std::cout << j << std::endl;

  return 0;
}