#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;
#define pb push_back
#define maxSize 30010
typedef long long ll;
typedef vector<ll> vi;
int arr[maxSize];
vector< int > tree[maxSize * 4];
vi::iterator it;
int bst(int i, int l, int r, int v){
int m = (l + r) / 2;
if(l==r){
if( tree[i][l] > v)
return 1;
else
return 0;
}
if( tree[i][m+1] > v){
return r - m + bst(i, l, m, v);
}
else
return bst(i, m+1, r, v);
}
void init(int node, int b, int e){
if(b==e){
// tree[node] =arr[b];
tree[node].pb(arr[b]);
return;
}
init(node*2, b, (b+e)/2);
init(node*2+1,(b+e)/2+1, e);
for (int i = b; i <=e; ++i) {
tree[node].push_back(arr[i]);
}
sort(tree[node].begin(), tree[node].end());
}
int query(int node, int b, int e, int i, int j, int v) {
if (j < b || e < i)
return 0;
if (b >= i && e <= j) {
return bst(node, 0, tree[node].size()-1, v);
}
return query(node*2, b, (b+e)/2, i, j, v ) + query(node*2+1, (b+e)/2+1, e, i, j, v );
}
int main()
{
int n,q;
scanf("%d",&n);
for (int i = 1; i <=n ; ++i) {
scanf("%d",&arr[i]);
}
init(1, 1, n);
cin>>q;
for (int j = 0; j <q ; ++j) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
printf("%d\n",query(1, 1, n, a, b, c));
}
return 0;
}
I2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxjY3R5cGU+CiNpbmNsdWRlIDxjbGltaXRzPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxsaXN0PgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8dXRpbGl0eT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgIG1heFNpemUgMzAwMTAKdHlwZWRlZiBsb25nICBsb25nIGxsOwoKdHlwZWRlZiB2ZWN0b3I8bGw+IHZpOwoKCgppbnQgYXJyW21heFNpemVdOwoKdmVjdG9yPCBpbnQgPiB0cmVlW21heFNpemUgKiA0XTsKCnZpOjppdGVyYXRvciBpdDsKCgppbnQgYnN0KGludCBpLCBpbnQgbCwgaW50IHIsIGludCB2KXsKCiAgICBpbnQgbSA9IChsICsgcikgLyAyOwoKICAgIGlmKGw9PXIpewogICAgICAgIGlmKCB0cmVlW2ldW2xdID4gdikKICAgICAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgZWxzZQogICAgICAgICAgICByZXR1cm4gMDsKICAgIH0KCiAgICBpZiggdHJlZVtpXVttKzFdID4gdil7CiAgICAgICAgcmV0dXJuICByIC0gbSArIGJzdChpLCBsLCBtLCB2KTsKICAgIH0KICAgIGVsc2UKICAgICAgICByZXR1cm4gYnN0KGksIG0rMSwgciwgdik7CgoKfQoKCnZvaWQgaW5pdChpbnQgbm9kZSwgaW50IGIsIGludCBlKXsKCiAgICAgICAgaWYoYj09ZSl7CiAgICAgICAgICAgLy8gdHJlZVtub2RlXSA9YXJyW2JdOwogICAgICAgICAgIHRyZWVbbm9kZV0ucGIoYXJyW2JdKTsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KCiAgICAgICAgaW5pdChub2RlKjIsIGIsIChiK2UpLzIpOwogICAgICAgIGluaXQobm9kZSoyKzEsKGIrZSkvMisxLCBlKTsKCgogICAgZm9yIChpbnQgaSA9IGI7IGkgPD1lOyArK2kpIHsKCiAgICAgICAgdHJlZVtub2RlXS5wdXNoX2JhY2soYXJyW2ldKTsKICAgIH0KCiAgICBzb3J0KHRyZWVbbm9kZV0uYmVnaW4oKSwgdHJlZVtub2RlXS5lbmQoKSk7CgoKfQoKaW50IHF1ZXJ5KGludCBub2RlLCBpbnQgYiwgaW50IGUsIGludCBpLCBpbnQgaiwgaW50IHYpIHsKCgogICAgaWYgKGogPCBiIHx8IGUgPCBpKQogICAgICAgIHJldHVybiAwOwoKICAgIGlmIChiID49IGkgJiYgZSA8PSBqKSB7CiAgICAgICAgcmV0dXJuIGJzdChub2RlLCAwLCB0cmVlW25vZGVdLnNpemUoKS0xLCB2KTsKICAgIH0KCiAgICByZXR1cm4gcXVlcnkobm9kZSoyLCBiLCAoYitlKS8yLCBpLCBqLCB2ICkgICsgcXVlcnkobm9kZSoyKzEsIChiK2UpLzIrMSwgZSwgaSwgaiwgdiApOwoKfQoKCmludCBtYWluKCkKewoKICAgIGludCBuLHE7CgogICAgc2NhbmYoIiVkIiwmbik7CgogICAgZm9yIChpbnQgaSA9IDE7IGkgPD1uIDsgKytpKSB7CgogICAgICAgIHNjYW5mKCIlZCIsJmFycltpXSk7CgogICAgfQoKICAgIGluaXQoMSwgMSwgbik7CgogICAgY2luPj5xOwoKICAgIGZvciAoaW50IGogPSAwOyBqIDxxIDsgKytqKSB7CiAgICAgICAgaW50IGEsYixjOwogICAgICAgIHNjYW5mKCIlZCVkJWQiLCZhLCZiLCZjKTsKICAgICAgICBwcmludGYoIiVkXG4iLHF1ZXJ5KDEsIDEsIG4sIGEsIGIsIGMpKTsKCiAgICB9CgoKCiAgICByZXR1cm4gMDsKfQ==