#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set;
typedef pair<int, int>pr;
#define all(i) i.begin() , i.end()
#define ft first
#define sn second
#define pb push_back
#define en "\n"
#define dbg cout<<"rony\n"
#define MAXN 30010
#define inf 1e6+5
const ll mod = 1e9 + 7;
int n;
int a[MAXN];
struct segment_tree
{
struct NODE {
int st , EN;
vector<int>v;
void init(int L, int R) {
st = L, EN = R;
if (L == R) v.pb(a[L]);
}
} g[3 * MAXN];
void merge(vector<int>&A, vector<int>&B, vector<int>&C)
{
int i = 0, j = 0;
while (i < B.size() && j < C.size())
{
if (B[i] < C[j]) {
A.pb(B[i]); i++;
}
else {
A.pb(C[j]); j++;
}
}
while (i < B.size()) {A.pb(B[i]); i++;}
while (j < C.size()) {A.pb(C[j]); j++;}
}
void fill_CN(NODE &CN, NODE &LN, NODE &RN) // fill_current_node
{
merge(CN.v, LN.v, RN.v);
}
void build(int CN, int L, int R)
{
g[CN].init(L, R);
if (L == R ) return;
int mid = (L + R) >> 1;
build(CN * 2, L, mid);
build(CN * 2 + 1, mid + 1, R);
fill_CN (g[CN], g[CN * 2] , g[CN * 2 + 1]);
}
int query(int CN, int L, int R, int val)
{
int x = g[CN].st;
int y = g[CN].EN;
if (y < L || x > R) return 0;
if (L <= x && R >= y ) {
int ub = upper_bound(all(g[CN].v), val) - g[CN].v.begin();
return (int)g[CN].v.size() - ub;
}
int LN = CN << 1;
int ans = query(LN, L, R, val);
ans += query(LN | 1, L, R, val);
return ans;
}
} s_tree;
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
s_tree.build(1, 1, n);
int q; cin >> q;
while (q--)
{
int l, r, x;
cin >> l >> r >> x;
cout << s_tree.query(1, l, r, x) << en;
}
}
int main()
{
IOS;
ll t;
t = 1;
// cin >> t;
int c = 0;
while ( t-- )
{
// cout<<"Case "<<++c<<": ";
solve();
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnR5cGVkZWYgbG9uZyBsb25nIGludCBsbDsKI2RlZmluZSBJT1MgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsgIGNpbi50aWUoMCk7IGNvdXQudGllKDApOwoKCiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwoKdHlwZWRlZiB0cmVlPGludCwgbnVsbF90eXBlLCBsZXNzPGludD4sIHJiX3RyZWVfdGFnLCB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGU+b3JkZXJfc2V0Owp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+cHI7CiNkZWZpbmUgYWxsKGkpICAgICBpLmJlZ2luKCkgLCBpLmVuZCgpCiNkZWZpbmUgZnQgICAgIGZpcnN0CiNkZWZpbmUgc24gICAgIHNlY29uZAojZGVmaW5lIHBiIHB1c2hfYmFjawoKI2RlZmluZSBlbiAiXG4iCiNkZWZpbmUgZGJnIGNvdXQ8PCJyb255XG4iCgojZGVmaW5lIE1BWE4gMzAwMTAKI2RlZmluZSBpbmYgMWU2KzUKY29uc3QgbGwgbW9kID0gMWU5ICsgNzsKCmludCBuOwppbnQgYVtNQVhOXTsKCnN0cnVjdCBzZWdtZW50X3RyZWUKewogICAgc3RydWN0IE5PREUgewogICAgICAgIGludCBzdCAsIEVOOwogICAgICAgIHZlY3RvcjxpbnQ+djsKCiAgICAgICAgdm9pZCBpbml0KGludCBMLCBpbnQgUikgewogICAgICAgICAgICBzdCA9IEwsIEVOID0gUjsKICAgICAgICAgICAgaWYgKEwgPT0gUikgdi5wYihhW0xdKTsKICAgICAgICB9CiAgICB9IGdbMyAqIE1BWE5dOwoKICAgIHZvaWQgbWVyZ2UodmVjdG9yPGludD4mQSwgdmVjdG9yPGludD4mQiwgdmVjdG9yPGludD4mQykKICAgIHsKICAgICAgICBpbnQgaSA9IDAsIGogPSAwOwogICAgICAgIHdoaWxlIChpIDwgQi5zaXplKCkgJiYgaiA8IEMuc2l6ZSgpKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKEJbaV0gPCBDW2pdKSB7CiAgICAgICAgICAgICAgICBBLnBiKEJbaV0pOyBpKys7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICBBLnBiKENbal0pOyBqKys7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHdoaWxlIChpIDwgQi5zaXplKCkpIHtBLnBiKEJbaV0pOyBpKys7fQogICAgICAgIHdoaWxlIChqIDwgQy5zaXplKCkpIHtBLnBiKENbal0pOyBqKys7fQogICAgfQoKICAgIHZvaWQgZmlsbF9DTihOT0RFICZDTiwgTk9ERSAmTE4sIE5PREUgJlJOKSAvLyBmaWxsX2N1cnJlbnRfbm9kZQogICAgewogICAgICAgIG1lcmdlKENOLnYsIExOLnYsIFJOLnYpOwogICAgfQoKICAgIHZvaWQgYnVpbGQoaW50IENOLCBpbnQgTCwgaW50IFIpCiAgICB7CiAgICAgICAgZ1tDTl0uaW5pdChMLCBSKTsKCiAgICAgICAgaWYgKEwgPT0gUiApIHJldHVybjsKICAgICAgICBpbnQgbWlkID0gKEwgKyBSKSA+PiAxOwoKICAgICAgICBidWlsZChDTiAqIDIsIEwsIG1pZCk7CiAgICAgICAgYnVpbGQoQ04gKiAyICsgMSwgbWlkICsgMSwgUik7CgogICAgICAgIGZpbGxfQ04gKGdbQ05dLCBnW0NOICogMl0gLCBnW0NOICogMiArIDFdKTsKICAgIH0KCiAgICBpbnQgcXVlcnkoaW50IENOLCBpbnQgTCwgaW50IFIsIGludCB2YWwpCiAgICB7CiAgICAgICAgaW50IHggPSBnW0NOXS5zdDsKICAgICAgICBpbnQgeSA9IGdbQ05dLkVOOwogICAgICAgIGlmICh5IDwgTCB8fCB4ID4gUikgcmV0dXJuIDA7CgogICAgICAgIGlmIChMIDw9IHggJiYgUiA+PSB5ICkgewogICAgICAgICAgICBpbnQgdWIgPSB1cHBlcl9ib3VuZChhbGwoZ1tDTl0udiksIHZhbCkgLSBnW0NOXS52LmJlZ2luKCk7CiAgICAgICAgICAgIHJldHVybiAoaW50KWdbQ05dLnYuc2l6ZSgpIC0gdWI7CiAgICAgICAgfQoKICAgICAgICBpbnQgTE4gPSBDTiA8PCAxOwoKICAgICAgICBpbnQgYW5zID0gcXVlcnkoTE4sIEwsIFIsIHZhbCk7CiAgICAgICAgYW5zICs9IHF1ZXJ5KExOIHwgMSwgTCwgUiwgdmFsKTsKICAgICAgICByZXR1cm4gYW5zOwogICAgfQoKfSBzX3RyZWU7CnZvaWQgc29sdmUoKQp7CiAgICBjaW4gPj4gbjsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgY2luID4+IGFbaV07CiAgICBzX3RyZWUuYnVpbGQoMSwgMSwgbik7CgogICAgaW50IHE7IGNpbiA+PiBxOwogICAgd2hpbGUgKHEtLSkKICAgIHsKICAgICAgICBpbnQgbCwgciwgeDsKICAgICAgICBjaW4gPj4gbCA+PiByID4+IHg7CiAgICAgICAgY291dCA8PCBzX3RyZWUucXVlcnkoMSwgbCwgciwgeCkgPDwgZW47CiAgICB9Cgp9CmludCBtYWluKCkKewogICAgSU9TOwogICAgbGwgdDsKICAgIHQgPSAxOwoKICAgIC8vIGNpbiA+PiB0OwoKICAgIGludCBjID0gMDsKICAgIHdoaWxlICggdC0tICkKICAgIHsKICAgICAgICAvLyBjb3V0PDwiQ2FzZSAiPDwrK2M8PCI6ICI7CiAgICAgICAgc29sdmUoKTsKICAgIH0KICAgIHJldHVybiAwOwp9