#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;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgoKI2RlZmluZSBpbnQgbG9uZyBsb25nCgovLyBDb2RlIGZvciBNbydzIEFsZ29yaXRobSBiYXNlZCBvbiBDUC1hbGdvcml0aG1zCgpjb25zdCBpbnQgYmxvY2tfc2l6ZSA9IDMyNTsKY29uc3QgaW50IE1BWE4gPSAxMDAwMDU7CgppbnQgbjsKaW50IGNvdW50W2Jsb2NrX3NpemVdOwppbnQgc3VtW2Jsb2NrX3NpemVdOwppbnQgbnVtW01BWE5dOwppbnQgY3RbTUFYTl07CmludCBzdFtNQVhOXTsKaW50IGFbTUFYTl07Cgp2b2lkIHVwZChpbnQgeCwgaW50IHYpIHsKICBpZih4ID09IDApCiAgICByZXR1cm47CgogIGN0W3hdICs9IHY7CiAgc3RbeF0gKz0gdiooeC0xKTsKICBjb3VudFt4L2Jsb2NrX3NpemVdICs9IHY7CiAgc3VtW3gvYmxvY2tfc2l6ZV0gKz0gdiooeC0xKTsKfQoKdm9pZCByZW1vdmUoaW50IGlkeCkgewogIHVwZChudW1bYVtpZHhdXSwgLTEpOwogIG51bVthW2lkeF1dLS07CiAgdXBkKG51bVthW2lkeF1dLCArMSk7Cn0KCnZvaWQgYWRkKGludCBpZHgpIHsKICB1cGQobnVtW2FbaWR4XV0sIC0xKTsKICBudW1bYVtpZHhdXSsrOwogIHVwZChudW1bYVtpZHhdXSwgKzEpOwp9CgppbnQgZ2V0X2Fuc3dlcihpbnQgaykgewogIGludCBqID0gMDsKICBpbnQgZG9uZSA9IDA7CgogIHdoaWxlKGogPCBibG9ja19zaXplICYmIHN1bVtqXSA8PSBrKSB7CiAgICBrIC09IHN1bVtqXTsKICAgIGRvbmUgKz0gY291bnRbal07CiAgICBqKys7CiAgfQoKICBpZihqID09IGJsb2NrX3NpemUpCiAgICByZXR1cm4gZG9uZTsKCiAgaW50IGlkID0gaipibG9ja19zaXplOwogIHdoaWxlKHN0W2lkXSA8PSBrKSB7CiAgICBrIC09IHN0W2lkXTsKICAgIGRvbmUgKz0gY3RbaWRdOwogICAgaWQrKzsKICB9CgogIGludCBhZGQgPSBrLyhpZC0xKTsKICByZXR1cm4gZG9uZSArIGFkZDsKfQoKc3RydWN0IFF1ZXJ5IHsKICBpbnQgbCwgciwgaWR4LCBrOwogIGJvb2wgb3BlcmF0b3I8KFF1ZXJ5IG90aGVyKSBjb25zdAogIHsKICAgIHJldHVybiBzdGQ6Om1ha2VfcGFpcihsIC8gYmxvY2tfc2l6ZSwgcikgPAogICAgICBzdGQ6Om1ha2VfcGFpcihvdGhlci5sIC8gYmxvY2tfc2l6ZSwgb3RoZXIucik7CiAgfQp9OwoKc3RkOjp2ZWN0b3I8aW50PiBtb19zX2FsZ29yaXRobShzdGQ6OnZlY3RvcjxRdWVyeT4gcXVlcmllcykgewogIHN0ZDo6dmVjdG9yPGludD4gYW5zd2VycyhxdWVyaWVzLnNpemUoKSk7CiAgc3RkOjpzb3J0KHF1ZXJpZXMuYmVnaW4oKSwgcXVlcmllcy5lbmQoKSk7CgogIGludCBjdXJfbCA9IDA7CiAgaW50IGN1cl9yID0gLTE7CgogIGZvciAoUXVlcnkgcSA6IHF1ZXJpZXMpIHsKICAgIHdoaWxlIChjdXJfbCA+IHEubCkgewogICAgICBjdXJfbC0tOwogICAgICBhZGQoY3VyX2wpOwogICAgfQogICAgd2hpbGUgKGN1cl9yIDwgcS5yKSB7CiAgICAgIGN1cl9yKys7CiAgICAgIGFkZChjdXJfcik7CiAgICB9CiAgICB3aGlsZSAoY3VyX2wgPCBxLmwpIHsKICAgICAgcmVtb3ZlKGN1cl9sKTsKICAgICAgY3VyX2wrKzsKICAgIH0KICAgIHdoaWxlIChjdXJfciA+IHEucikgewogICAgICByZW1vdmUoY3VyX3IpOwogICAgICBjdXJfci0tOwogICAgfQogICAgYW5zd2Vyc1txLmlkeF0gPSBnZXRfYW5zd2VyKHEuayk7CiAgfQogIHJldHVybiBhbnN3ZXJzOwp9CgpzaWduZWQgbWFpbigpIHsKICBzdGQ6Omlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICBzdGQ6OmNpbi50aWUoMCk7CgogIHN0ZDo6Y2luID4+IG47CgogIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICBzdGQ6OmNpbiA+PiBhW2ldOwoKICBzdGQ6OnZlY3RvcjxRdWVyeT4gcXM7CiAgaW50IHE7CiAgc3RkOjpjaW4gPj4gcTsKCiAgZm9yKGludCBpID0gMDsgaSA8IHE7IGkrKykgewogICAgaW50IGwsIHIsIGs7CiAgICBzdGQ6OmNpbiA+PiBsID4+IHIgPj4gazsKICAgIGwtLTsgci0tOwogICAgcXMucHVzaF9iYWNrKHtsLCByLCBpLCBrfSk7CiAgfQoKICBzdGQ6OnZlY3RvcjxpbnQ+IGFucyA9IG1vX3NfYWxnb3JpdGhtKHFzKTsKCiAgZm9yKGludCBqIDogYW5zKQogICAgc3RkOjpjb3V0IDw8IGogPDwgc3RkOjplbmRsOwoKICByZXR1cm4gMDsKfQ==