#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
class ImplicitSegmentTree {
int sz;
struct Node {
int s;
Node *l, *r;
Node() : s(0), l(0), r(0) {}
} *root;
int query(Node *v, int vl, int vr, int l, int r) const {
if (!v || r < vl || vr < l)
return 0;
if (l <= vl && vr <= r)
return v->s;
int vm = vl + (vr - vl) / 2;
int ql = query(v->l, vl, vm, l, r);
int qr = query(v->r, vm + 1, vr, l, r);
return ql + qr;
}
void modify(Node *v, int vl, int vr, int pos, int val) {
if (vl == vr) {
v->s += val;
return;
}
int vm = vl + (vr - vl) / 2;
if (pos <= vm) {
if (!v->l)
v->l = new Node();
modify(v->l, vl, vm, pos, val);
} else {
if (!v->r)
v->r = new Node();
modify(v->r, vm + 1, vr, pos, val);
}
v->s = (v->l ? v->l->s : 0) + (v->r ? v->r->s : 0);
}
void destroy(Node *v) {
if (v->l)
destroy(v->l);
if (v->r)
destroy(v->r);
delete v;
}
public:
ImplicitSegmentTree(int size) {
sz = size;
root = new Node();
}
~ImplicitSegmentTree() {
destroy(root);
}
int size() {
return sz;
}
int query(int l, int r) const {
return query(root, 0, sz - 1, l, r);
}
void modify(int pos, int val) {
modify(root, 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(ImplicitSegmentTree &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]));
}
ImplicitSegmentTree 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+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgoKY2xhc3MgSW1wbGljaXRTZWdtZW50VHJlZSB7CgogICAgaW50IHN6OwogICAgc3RydWN0IE5vZGUgewogICAgICAgIGludCBzOwogICAgICAgIE5vZGUgKmwsICpyOwogICAgICAgIE5vZGUoKSA6IHMoMCksIGwoMCksIHIoMCkge30KICAgIH0gKnJvb3Q7CgogICAgaW50IHF1ZXJ5KE5vZGUgKnYsIGludCB2bCwgaW50IHZyLCBpbnQgbCwgaW50IHIpIGNvbnN0IHsKICAgICAgICBpZiAoIXYgfHwgciA8IHZsIHx8IHZyIDwgbCkKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgaWYgKGwgPD0gdmwgJiYgdnIgPD0gcikKICAgICAgICAgICAgcmV0dXJuIHYtPnM7CiAgICAgICAgaW50IHZtID0gdmwgKyAodnIgLSB2bCkgLyAyOwogICAgICAgIGludCBxbCA9IHF1ZXJ5KHYtPmwsIHZsLCB2bSwgbCwgcik7CiAgICAgICAgaW50IHFyID0gcXVlcnkodi0+ciwgdm0gKyAxLCB2ciwgbCwgcik7CiAgICAgICAgcmV0dXJuIHFsICsgcXI7CiAgICB9CgogICAgdm9pZCBtb2RpZnkoTm9kZSAqdiwgaW50IHZsLCBpbnQgdnIsIGludCBwb3MsIGludCB2YWwpIHsKICAgICAgICBpZiAodmwgPT0gdnIpIHsKICAgICAgICAgICAgdi0+cyArPSB2YWw7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgaW50IHZtID0gdmwgKyAodnIgLSB2bCkgLyAyOwogICAgICAgIGlmIChwb3MgPD0gdm0pIHsKICAgICAgICAgICAgaWYgKCF2LT5sKQogICAgICAgICAgICAgICAgdi0+bCA9IG5ldyBOb2RlKCk7CiAgICAgICAgICAgIG1vZGlmeSh2LT5sLCB2bCwgdm0sIHBvcywgdmFsKTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBpZiAoIXYtPnIpCiAgICAgICAgICAgICAgICB2LT5yID0gbmV3IE5vZGUoKTsKICAgICAgICAgICAgbW9kaWZ5KHYtPnIsIHZtICsgMSwgdnIsIHBvcywgdmFsKTsKICAgICAgICB9CiAgICAgICAgdi0+cyA9ICh2LT5sID8gdi0+bC0+cyA6IDApICsgKHYtPnIgPyB2LT5yLT5zIDogMCk7CiAgICB9CgogICAgdm9pZCBkZXN0cm95KE5vZGUgKnYpIHsKICAgICAgICBpZiAodi0+bCkKICAgICAgICAgICAgZGVzdHJveSh2LT5sKTsKICAgICAgICBpZiAodi0+cikKICAgICAgICAgICAgZGVzdHJveSh2LT5yKTsKICAgICAgICBkZWxldGUgdjsKICAgIH0KCnB1YmxpYzoKCiAgICBJbXBsaWNpdFNlZ21lbnRUcmVlKGludCBzaXplKSB7CiAgICAgICAgc3ogPSBzaXplOwogICAgICAgIHJvb3QgPSBuZXcgTm9kZSgpOwogICAgfQoKICAgIH5JbXBsaWNpdFNlZ21lbnRUcmVlKCkgewogICAgICAgIGRlc3Ryb3kocm9vdCk7CiAgICB9CgogICAgaW50IHNpemUoKSB7CiAgICAgICAgcmV0dXJuIHN6OwogICAgfQoKICAgIGludCBxdWVyeShpbnQgbCwgaW50IHIpIGNvbnN0IHsKICAgICAgICByZXR1cm4gcXVlcnkocm9vdCwgMCwgc3ogLSAxLCBsLCByKTsKICAgIH0KCiAgICB2b2lkIG1vZGlmeShpbnQgcG9zLCBpbnQgdmFsKSB7CiAgICAgICAgbW9kaWZ5KHJvb3QsIDAsIHN6IC0gMSwgcG9zLCB2YWwpOwogICAgfQoKfTsKCgpjbGFzcyBFdmVudCB7CgogICAgaW50IHR5cGUsIGluZGV4LCB4LCB5OwoKcHVibGljOgoKICAgIEV2ZW50KGludCB0eXBlLCBpbnQgaW5kZXgsIGludCB4LCBpbnQgeSkgOiB0eXBlKHR5cGUpLCBpbmRleChpbmRleCksIHgoeCksIHkoeSkge30KICAgIAogICAgYm9vbCBvcGVyYXRvciA8IChjb25zdCBFdmVudCAmdGhhdCkgY29uc3QgewogICAgICAgIHJldHVybiB4IDwgdGhhdC54IHx8IHggPT0gdGhhdC54ICYmIHR5cGUgPCB0aGF0LnR5cGU7CiAgICB9CgogICAgdm9pZCBwcm9jZXNzKEltcGxpY2l0U2VnbWVudFRyZWUgJnN0LCB2ZWN0b3I8aW50PiAmYW5zd2VycykgY29uc3QgewogICAgICAgIGludCBrID0gc3QucXVlcnkoeSArIDEsIHN0LnNpemUoKSAtIDEpOwogICAgICAgIGlmICh0eXBlID09IDEpCiAgICAgICAgICAgIGFuc3dlcnNbaW5kZXhdIC09IHN0LnF1ZXJ5KHkgKyAxLCBzdC5zaXplKCkgLSAxKTsKICAgICAgICBpZiAodHlwZSA9PSAyKQogICAgICAgICAgICBzdC5tb2RpZnkoeSwgMSk7CiAgICAgICAgaWYgKHR5cGUgPT0gMykKICAgICAgICAgICAgYW5zd2Vyc1tpbmRleF0gKz0gc3QucXVlcnkoeSArIDEsIHN0LnNpemUoKSAtIDEpOwogICAgfQoKfTsKCgppbnQgbWFpbigpIHsKICAgIHZlY3RvcjxFdmVudD4gc2NhbkxpbmU7CgogICAgaW50IGFTaXplLCBhTWF4ID0gMDsKICAgIHNjYW5mKCIlZCIsICZhU2l6ZSk7CgogICAgdmVjdG9yPGludD4gYShhU2l6ZSk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IGFTaXplOyBpKyspIHsKICAgICAgICBzY2FuZigiJWQiLCAmYVtpXSk7CiAgICAgICAgYU1heCA9IG1heChhTWF4LCBhW2ldKTsKICAgICAgICBzY2FuTGluZS5wdXNoX2JhY2soRXZlbnQoMiwgLTEsIGksIGFbaV0pKTsKICAgIH0KCiAgICBJbXBsaWNpdFNlZ21lbnRUcmVlIHN0KGFNYXggKyAxKTsKCiAgICBpbnQgcXVlcmllc0NvdW50OwogICAgc2NhbmYoIiVkIiwgJnF1ZXJpZXNDb3VudCk7CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBxdWVyaWVzQ291bnQ7IGkrKykgewogICAgICAgIGludCBsLCByLCBrOwogICAgICAgIHNjYW5mKCIlZCVkJWQiLCAmbCwgJnIsICZrKTsKICAgICAgICBzY2FuTGluZS5wdXNoX2JhY2soRXZlbnQoMSwgaSwgbCAtIDEsIGspKTsKICAgICAgICBzY2FuTGluZS5wdXNoX2JhY2soRXZlbnQoMywgaSwgciAtIDEsIGspKTsKICAgIH0KCiAgICB2ZWN0b3I8aW50PiBhbnN3ZXJzKHF1ZXJpZXNDb3VudCk7CiAgICBzb3J0KHNjYW5MaW5lLmJlZ2luKCksIHNjYW5MaW5lLmVuZCgpKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2NhbkxpbmUuc2l6ZSgpOyBpKyspCiAgICAgICAgc2NhbkxpbmVbaV0ucHJvY2VzcyhzdCwgYW5zd2Vycyk7CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBxdWVyaWVzQ291bnQ7IGkrKykKICAgICAgICBwcmludGYoIiVkXG4iLCBhbnN3ZXJzW2ldKTsKfQ==