#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(int size) {
sz = size;
t.resize(4 * sz);
}
int size() {
return 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, x, y;
public:
Event(int type, int index, int x, int y) : type(type), index(index), x(x), y(y) {}
bool operator < (const Event &that) const {
return x < that.x || x == that.x && type < that.type;
}
void process(SegmentTree &st, vector<int> &answers) const {
int k = st.query(y + 1, st.size() - 1);
if (type == 1)
answers[index] -= st.query(y + 1, st.size() - 1);
if (type == 2)
st.modify(y, 1);
if (type == 3)
answers[index] += st.query(y + 1, st.size() - 1);
}
};
int main() {
vector<Event> scanLine;
int aSize, aMax = 0;
scanf("%d", &aSize);
vector<int> a(aSize);
for (int i = 0; i < aSize; i++) {
scanf("%d", &a[i]);
aMax = max(aMax, a[i]);
scanLine.push_back(Event(2, -1, i, a[i]));
}
SegmentTree st(aMax + 1);
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 - 1, k));
scanLine.push_back(Event(3, i, r - 1, 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+IHQ7CgogICAgaW50IHF1ZXJ5KGludCB2LCBpbnQgdmwsIGludCB2ciwgaW50IGwsIGludCByKSBjb25zdCB7CiAgICAgICAgaWYgKHIgPCB2bCB8fCB2ciA8IGwpCiAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIGlmIChsIDw9IHZsICYmIHZyIDw9IHIpCiAgICAgICAgICAgIHJldHVybiB0W3ZdOwogICAgICAgIGludCB2bSA9IHZsICsgKHZyIC0gdmwpIC8gMjsKICAgICAgICBpbnQgcWwgPSBxdWVyeSgyICogdiArIDEsIHZsLCB2bSwgbCwgcik7CiAgICAgICAgaW50IHFyID0gcXVlcnkoMiAqIHYgKyAyLCB2bSArIDEsIHZyLCBsLCByKTsKICAgICAgICByZXR1cm4gcWwgKyBxcjsKICAgIH0KCiAgICB2b2lkIG1vZGlmeShpbnQgdiwgaW50IHZsLCBpbnQgdnIsIGludCBwb3MsIGludCB2YWwpIHsKICAgICAgICBpZiAodmwgPT0gdnIpIHsKICAgICAgICAgICAgdFt2XSArPSB2YWw7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgaW50IHZtID0gdmwgKyAodnIgLSB2bCkgLyAyOwogICAgICAgIGlmIChwb3MgPD0gdm0pCiAgICAgICAgICAgIG1vZGlmeSgyICogdiArIDEsIHZsLCB2bSwgcG9zLCB2YWwpOwogICAgICAgIGVsc2UKICAgICAgICAgICAgbW9kaWZ5KDIgKiB2ICsgMiwgdm0gKyAxLCB2ciwgcG9zLCB2YWwpOwogICAgICAgIHRbdl0gPSB0WzIgKiB2ICsgMV0gKyB0WzIgKiB2ICsgMl07CiAgICB9CgpwdWJsaWM6CgogICAgU2VnbWVudFRyZWUoaW50IHNpemUpIHsKICAgICAgICBzeiA9IHNpemU7CiAgICAgICAgdC5yZXNpemUoNCAqIHN6KTsKICAgIH0KCiAgICBpbnQgc2l6ZSgpIHsKICAgICAgICByZXR1cm4gc3o7CiAgICB9CgogICAgaW50IHF1ZXJ5KGludCBsLCBpbnQgcikgY29uc3QgewogICAgICAgIHJldHVybiBxdWVyeSgwLCAwLCBzeiAtIDEsIGwsIHIpOwogICAgfQoKICAgIHZvaWQgbW9kaWZ5KGludCBwb3MsIGludCB2YWwpIHsKICAgICAgICBtb2RpZnkoMCwgMCwgc3ogLSAxLCBwb3MsIHZhbCk7CiAgICB9Cgp9OwoKCmNsYXNzIEV2ZW50IHsKCiAgICBpbnQgdHlwZSwgaW5kZXgsIHgsIHk7CgpwdWJsaWM6CgogICAgRXZlbnQoaW50IHR5cGUsIGludCBpbmRleCwgaW50IHgsIGludCB5KSA6IHR5cGUodHlwZSksIGluZGV4KGluZGV4KSwgeCh4KSwgeSh5KSB7fQogICAgCiAgICBib29sIG9wZXJhdG9yIDwgKGNvbnN0IEV2ZW50ICZ0aGF0KSBjb25zdCB7CiAgICAgICAgcmV0dXJuIHggPCB0aGF0LnggfHwgeCA9PSB0aGF0LnggJiYgdHlwZSA8IHRoYXQudHlwZTsKICAgIH0KCiAgICB2b2lkIHByb2Nlc3MoU2VnbWVudFRyZWUgJnN0LCB2ZWN0b3I8aW50PiAmYW5zd2VycykgY29uc3QgewogICAgICAgIGludCBrID0gc3QucXVlcnkoeSArIDEsIHN0LnNpemUoKSAtIDEpOwogICAgICAgIGlmICh0eXBlID09IDEpCiAgICAgICAgICAgIGFuc3dlcnNbaW5kZXhdIC09IHN0LnF1ZXJ5KHkgKyAxLCBzdC5zaXplKCkgLSAxKTsKICAgICAgICBpZiAodHlwZSA9PSAyKQogICAgICAgICAgICBzdC5tb2RpZnkoeSwgMSk7CiAgICAgICAgaWYgKHR5cGUgPT0gMykKICAgICAgICAgICAgYW5zd2Vyc1tpbmRleF0gKz0gc3QucXVlcnkoeSArIDEsIHN0LnNpemUoKSAtIDEpOwogICAgfQoKfTsKCgppbnQgbWFpbigpIHsKICAgIHZlY3RvcjxFdmVudD4gc2NhbkxpbmU7CgogICAgaW50IGFTaXplLCBhTWF4ID0gMDsKICAgIHNjYW5mKCIlZCIsICZhU2l6ZSk7CgogICAgdmVjdG9yPGludD4gYShhU2l6ZSk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IGFTaXplOyBpKyspIHsKICAgICAgICBzY2FuZigiJWQiLCAmYVtpXSk7CiAgICAgICAgYU1heCA9IG1heChhTWF4LCBhW2ldKTsKICAgICAgICBzY2FuTGluZS5wdXNoX2JhY2soRXZlbnQoMiwgLTEsIGksIGFbaV0pKTsKICAgIH0KCiAgICBTZWdtZW50VHJlZSBzdChhTWF4ICsgMSk7CgogICAgaW50IHF1ZXJpZXNDb3VudDsKICAgIHNjYW5mKCIlZCIsICZxdWVyaWVzQ291bnQpOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgcXVlcmllc0NvdW50OyBpKyspIHsKICAgICAgICBpbnQgbCwgciwgazsKICAgICAgICBzY2FuZigiJWQlZCVkIiwgJmwsICZyLCAmayk7CiAgICAgICAgc2NhbkxpbmUucHVzaF9iYWNrKEV2ZW50KDEsIGksIGwgLSAxLCBrKSk7CiAgICAgICAgc2NhbkxpbmUucHVzaF9iYWNrKEV2ZW50KDMsIGksIHIgLSAxLCBrKSk7CiAgICB9CgogICAgdmVjdG9yPGludD4gYW5zd2VycyhxdWVyaWVzQ291bnQpOwogICAgc29ydChzY2FuTGluZS5iZWdpbigpLCBzY2FuTGluZS5lbmQoKSk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHNjYW5MaW5lLnNpemUoKTsgaSsrKQogICAgICAgIHNjYW5MaW5lW2ldLnByb2Nlc3Moc3QsIGFuc3dlcnMpOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgcXVlcmllc0NvdW50OyBpKyspCiAgICAgICAgcHJpbnRmKCIlZFxuIiwgYW5zd2Vyc1tpXSk7Cn0=