SPOJ KQUERY

//chtholly and emilia will carry me to cm
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <array>
#include <tuple>

#define ll long long
#define lb long double
#define sz(vec) ((int)(vec.size()))
#define all(x) x.begin(), x.end()
#define LC(k) (2*(k) +1)
#define RC(k) (2*(k) +2)

const lb eps = 1e-9;
const ll mod = 1e9 + 7, ll_max = 1e18;
//const ll mod = (1 << (23)) * 119 +1;
const int MX = 3e5 +10, int_max = 0x3f3f3f3f;

using namespace std;

//i will learn from moo.
/* Input */
template<class T> void read(T &x) { cin >> x; }
template<class H, class T> void read(pair<H, T> &p) { cin >> p.first >> p.second; }
template<class T, size_t S> void read(array<T, S> &a) { for (T &i : a) read(i); }
template<class T> void read(vector<T> &v) { for (T &i : v) read(i); }

template<class H, class... T> void read(H &h, T &...t) { read(h); read(t...); }

/* Output */
template<class H, class T> ostream &operator<<(ostream &o, pair<H, T> &p) { o << p.first << " " << p.second; return o; }
template<class T, size_t S> ostream &operator<<(ostream &o, array<T, S> &a) { string s; for (T i : a) o << s << i, s = " "; return o; }
template<class T> ostream &operator<<(ostream &o, vector<T> &v) { string s; for (T i : v) o << s << i, s = " "; return o; }

template<class T> void write(T x) { cout << x; }
template<class H, class... T> void write(const H &h, const T &...t) { write(h); write(t...); }

void print() { write('\n'); }
template<class H, class... T> void print(const H &h, const T &...t) { write(h); if (sizeof...(t)) write(' '); print(t...); }

/* Misc */
template <typename T> void ckmin(T &a, const T &b) { a = min(a, b); }
template <typename T> void ckmax(T &a, const T &b) { a = max(a, b); }

int sum[MX*4], arr[MX], srt[MX*2], ans[MX];
int n, q, mm;

vector<pair<int, int>> adj[MX*2];

void U(int k, int v){
    for(; k<=mm*2; k += (k&(-k))) sum[k] += v;
}
int S(int k){
    return (!k) ? 0 : (sum[k] + S(k - (k&(-k))));
}

int llb(int k){
    return 1 + lower_bound(srt, srt + mm, k) - srt;
}

void solve(){
    read(n);
    for(int i = 0; i<n; i++) read(arr[i]);
    read(q);
    for(int i = 0; i<q; i++){
        int a, b, c;
        read(a, b, c);
        srt[i] = c;
        if(a > 1) adj[a - 2].push_back(make_pair(-c, i));
        adj[b - 1].push_back(make_pair(c, i));
    }
    for(int i = 0; i<n; i++) srt[q+i] = arr[i];
    srt[n+q] = int_max;
    sort(srt, srt + n+q+1);
    mm = unique(srt, srt + n+q+1) - srt;
    //print(vector<int>(srt, srt + mm));
    for(int i = 0; i<n; i++){
        U(llb(arr[i]), 1);
        for(auto e : adj[i]){
            int x = e.first, j = e.second;
            int v = x/abs(x);
            x /= v;
            ans[j] += v * (S(llb(int_max)) - S(llb(x)));
            //print(x, i, v, S(llb(x)), llb(x));
        }
    }
    for(int i = 0; i<q; i++){
        print(ans[i]);
    }
}

int main(){
  cin.tie(0) -> sync_with_stdio(0);
    int T = 1;
    //cin >> T;
  while(T--){
        solve();
    }
    return 0;
}