#include <bits/stdc++.h>
#define DEBUG // cerr << "Passed Line " << __LINE__ << "\n"
#define DEBUGX cerr << "Passed Line " << __LINE__ << "\n"
using namespace std;
const int N = 1e5 + 5; 
const int B = 150; 

int n, m, t, a[N], c[N], pos[N], L[N], R[N]; 
int die[N]; // i 被赶出队列的时间
struct Operation {
    int l, r, x; 
} Q[N]; 

struct Fenwick {
    int C[N]; 
    inline void add(int x, int k) { for (; x < N; x += x & -x) C[x] += k; }
    inline int sum(int x) { int r = 0; for (; x; x -= x & -x) r += C[x]; return r; }
    inline int sum(int l, int r) { return sum(r) - sum(l - 1); }
} F; 
vector<int> S[N], QS[N]; 

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> a[i]; 
    for (int i = 1; i <= m; ++i) cin >> Q[i].l >> Q[i].r >> Q[i].x; 
    for (int i = 1; i <= n; ++i) pos[i] = (i - 1) / B + 1; 
    t = pos[n]; 
    DEBUG; 
    for (int i = 1; i <= t; ++i) {
        L[i] = R[i - 1] + 1, R[i] = min(i * B, n); 
        int mx = -1, tag = 0; // 整块 push mx 次之后会直接爆炸
        for (int k = L[i]; k <= R[i]; ++k) mx = max(mx, c[k] = a[k] + 1); 
        for (int j = 1, k = 1; j <= m; ++j) {
            DEBUG; 
            auto modify = [&](int l, int r, int v) -> void {
                if (l > r) return; 
                if (l == L[i] && r == R[i]) return tag += v, void(); 
                for (int I = l; I <= r; ++I) c[I] -= v; 
                mx = -1; 
                for (int I = L[i]; I <= R[i]; ++I) mx = max(mx, c[I]); 
            }; 
            while (k <= m && tag < mx) modify(max(Q[k].l, L[i]), min(R[i], Q[k].r), 1), ++k; 
            if (Q[j].l <= L[i] && R[i] <= Q[j].r) {
                if (tag >= mx) die[j] = max(die[j], k - 1); // k - 1 爆掉
                else die[j] = m + 1; 
            }
            modify(max(Q[j].l, L[i]), min(R[i], Q[j].r), -1); 
        }
        DEBUG; 
    }
    for (int i = 1; i <= m; ++i) {
        int p = pos[Q[i].l], q = pos[Q[i].r]; 
        S[Q[i].l].emplace_back(i); S[Q[i].r + 1].emplace_back(-i); 
        QS[p].emplace_back(i); QS[q].emplace_back(i); 
    }
    for (int i = 1; i <= n; ++i) {
        DEBUG; 
        for (int x : S[i])
            if (x > 0) F.add(x, 1); 
            else F.add(-x, -1); 
        for (int id : QS[pos[i]]) if (Q[id].l <= i && i <= Q[id].r) {
            int l = id, r = m + 1; 
            // if (i == 1) cerr << "Find " << F.sum(1, 3) << "\n"; 
            while (l + 1 != r) {
                DEBUG; 
                int mid = l + r >> 1; 
                if (F.sum(id, mid) > a[i]) r = mid; 
                else l = mid; 
                DEBUG; 
            }
            die[id] = max(die[id], r); 
            // if (r == 5) cerr << "Query " << id << " on " << i << "\n"; 
            DEBUG; 
        }
    }
    DEBUG; 

    // for (int i = 1; i <= m; ++i) cerr << die[i] << "\n"; 
    // return 0; 

    vector<vector<pair<int, int>>> vec(N, vector<pair<int, int>>()); 
    vector<int> ans(m + 5); 
    for (int i = 1; i <= m; ++i) if (i <= die[i] - 1) vec[Q[i].x].emplace_back(i, die[i] - 1); 
    DEBUG; 
    for (int i = 1; i < N; ++i) if (vec[i].size()) {
        // DEBUGX; 
        for (int l = 0; l < vec[i].size(); ) {
            int r = l, mxr = vec[i][l].second; 
            // cerr << r << " " << mxr << "\n"; 
            while (r + 1 < vec[i].size() && vec[i][r + 1].first <= mxr) mxr = max(mxr, vec[i][++r].second); 
            ++ans[vec[i][l].first], --ans[mxr + 1]; 
            l = r + 1; 
        }
    }
    for (int i = 1; i <= m; ++i) ans[i] += ans[i - 1]; 
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n"; 
    return 0;
}