#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
class SegmentTree {
int sz;
vector<int> t;
int query(int v, int vl, int vr, int l, int r) const {
if (r < vl || vr < l)
return 0;
if (l <= vl && vr <= r)
return t[v];
int vm = vl + (vr - vl) / 2;
int ql = query(2 * v + 1, vl, vm, l, r);
int qr = query(2 * v + 2, vm + 1, vr, l, r);
return ql + qr;
}
void modify(int v, int vl, int vr, int pos, int val) {
if (vl == vr) {
t[v] += val;
return;
}
int vm = vl + (vr - vl) / 2;
if (pos <= vm)
modify(2 * v + 1, vl, vm, pos, val);
else
modify(2 * v + 2, vm + 1, vr, pos, val);
t[v] = t[2 * v + 1] + t[2 * v + 2];
}
public:
SegmentTree(const vector<int> &a) {
sz = a.size();
t.resize(4 * sz);
}
int query(int l, int r) const {
return query(0, 0, sz - 1, l, r);
}
void modify(int pos, int val) {
modify(0, 0, sz - 1, pos, val);
}
};
class Event {
int type, index, xl, xr, y;
public:
Event(int type, int index, int xl, int xr, int y) : type(type), index(index), xl(xl), xr(xr), y(y) {}
bool operator < (const Event &that) const {
return y > that.y || y == that.y && type < that.type;
}
void process(SegmentTree &st, vector<int> &answers) const {
if (type == 1)
answers[index] = st.query(xl, xr);
if (type == 2)
st.modify(xl, 1);
}
};
int main() {
vector<Event> scanLine;
int aSize;
scanf("%d", &aSize);
vector<int> a(aSize);
for (int i = 0; i < aSize; i++) {
scanf("%d", &a[i]);
scanLine.push_back(Event(2, -1, i, -1, a[i]));
}
SegmentTree st(a);
int queriesCount;
scanf("%d", &queriesCount);
for (int i = 0; i < queriesCount; i++) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
scanLine.push_back(Event(1, i, l, r, k));
}
vector<int> answers(queriesCount);
sort(scanLine.begin(), scanLine.end());
for (int i = 0; i < scanLine.size(); i++)
scanLine[i].process(st, answers);
for (int i = 0; i < queriesCount; i++)
printf("%d\n", answers[i]);
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx2ZWN0b3I+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgoKY2xhc3MgU2VnbWVudFRyZWUgewoKICAgIGludCBzejsKICAgIHZlY3RvcjxpbnQ+IHQ7CgogICAgaW50IHF1ZXJ5KGludCB2LCBpbnQgdmwsIGludCB2ciwgaW50IGwsIGludCByKSBjb25zdCB7CiAgICAgICAgaWYgKHIgPCB2bCB8fCB2ciA8IGwpCiAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIGlmIChsIDw9IHZsICYmIHZyIDw9IHIpCiAgICAgICAgICAgIHJldHVybiB0W3ZdOwogICAgICAgIGludCB2bSA9IHZsICsgKHZyIC0gdmwpIC8gMjsKICAgICAgICBpbnQgcWwgPSBxdWVyeSgyICogdiArIDEsIHZsLCB2bSwgbCwgcik7CiAgICAgICAgaW50IHFyID0gcXVlcnkoMiAqIHYgKyAyLCB2bSArIDEsIHZyLCBsLCByKTsKICAgICAgICByZXR1cm4gcWwgKyBxcjsKICAgIH0KCiAgICB2b2lkIG1vZGlmeShpbnQgdiwgaW50IHZsLCBpbnQgdnIsIGludCBwb3MsIGludCB2YWwpIHsKICAgICAgICBpZiAodmwgPT0gdnIpIHsKICAgICAgICAgICAgdFt2XSArPSB2YWw7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgaW50IHZtID0gdmwgKyAodnIgLSB2bCkgLyAyOwogICAgICAgIGlmIChwb3MgPD0gdm0pCiAgICAgICAgICAgIG1vZGlmeSgyICogdiArIDEsIHZsLCB2bSwgcG9zLCB2YWwpOwogICAgICAgIGVsc2UKICAgICAgICAgICAgbW9kaWZ5KDIgKiB2ICsgMiwgdm0gKyAxLCB2ciwgcG9zLCB2YWwpOwogICAgICAgIHRbdl0gPSB0WzIgKiB2ICsgMV0gKyB0WzIgKiB2ICsgMl07CiAgICB9CgpwdWJsaWM6CgogICAgU2VnbWVudFRyZWUoY29uc3QgdmVjdG9yPGludD4gJmEpIHsKICAgICAgICBzeiA9IGEuc2l6ZSgpOwogICAgICAgIHQucmVzaXplKDQgKiBzeik7CiAgICB9CgogICAgaW50IHF1ZXJ5KGludCBsLCBpbnQgcikgY29uc3QgewogICAgICAgIHJldHVybiBxdWVyeSgwLCAwLCBzeiAtIDEsIGwsIHIpOwogICAgfQoKICAgIHZvaWQgbW9kaWZ5KGludCBwb3MsIGludCB2YWwpIHsKICAgICAgICBtb2RpZnkoMCwgMCwgc3ogLSAxLCBwb3MsIHZhbCk7CiAgICB9Cgp9OwoKCmNsYXNzIEV2ZW50IHsKCiAgICBpbnQgdHlwZSwgaW5kZXgsIHhsLCB4ciwgeTsKCnB1YmxpYzoKCiAgICBFdmVudChpbnQgdHlwZSwgaW50IGluZGV4LCBpbnQgeGwsIGludCB4ciwgaW50IHkpIDogdHlwZSh0eXBlKSwgaW5kZXgoaW5kZXgpLCB4bCh4bCksIHhyKHhyKSwgeSh5KSB7fQogICAgCiAgICBib29sIG9wZXJhdG9yIDwgKGNvbnN0IEV2ZW50ICZ0aGF0KSBjb25zdCB7CiAgICAgICAgcmV0dXJuIHkgPiB0aGF0LnkgfHwgeSA9PSB0aGF0LnkgJiYgdHlwZSA8IHRoYXQudHlwZTsKICAgIH0KCiAgICB2b2lkIHByb2Nlc3MoU2VnbWVudFRyZWUgJnN0LCB2ZWN0b3I8aW50PiAmYW5zd2VycykgY29uc3QgewogICAgICAgIGlmICh0eXBlID09IDEpCiAgICAgICAgICAgIGFuc3dlcnNbaW5kZXhdID0gc3QucXVlcnkoeGwsIHhyKTsKICAgICAgICBpZiAodHlwZSA9PSAyKQogICAgICAgICAgICBzdC5tb2RpZnkoeGwsIDEpOwogICAgfQoKfTsKCgppbnQgbWFpbigpIHsKICAgIHZlY3RvcjxFdmVudD4gc2NhbkxpbmU7CgogICAgaW50IGFTaXplOwogICAgc2NhbmYoIiVkIiwgJmFTaXplKTsKCiAgICB2ZWN0b3I8aW50PiBhKGFTaXplKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgYVNpemU7IGkrKykgewogICAgICAgIHNjYW5mKCIlZCIsICZhW2ldKTsKICAgICAgICBzY2FuTGluZS5wdXNoX2JhY2soRXZlbnQoMiwgLTEsIGksIC0xLCBhW2ldKSk7CiAgICB9CgogICAgU2VnbWVudFRyZWUgc3QoYSk7CgogICAgaW50IHF1ZXJpZXNDb3VudDsKICAgIHNjYW5mKCIlZCIsICZxdWVyaWVzQ291bnQpOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgcXVlcmllc0NvdW50OyBpKyspIHsKICAgICAgICBpbnQgbCwgciwgazsKICAgICAgICBzY2FuZigiJWQlZCVkIiwgJmwsICZyLCAmayk7CiAgICAgICAgc2NhbkxpbmUucHVzaF9iYWNrKEV2ZW50KDEsIGksIGwsIHIsIGspKTsKICAgIH0KCiAgICB2ZWN0b3I8aW50PiBhbnN3ZXJzKHF1ZXJpZXNDb3VudCk7CiAgICBzb3J0KHNjYW5MaW5lLmJlZ2luKCksIHNjYW5MaW5lLmVuZCgpKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2NhbkxpbmUuc2l6ZSgpOyBpKyspCiAgICAgICAgc2NhbkxpbmVbaV0ucHJvY2VzcyhzdCwgYW5zd2Vycyk7CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBxdWVyaWVzQ291bnQ7IGkrKykKICAgICAgICBwcmludGYoIiVkXG4iLCBhbnN3ZXJzW2ldKTsKfQ==