#include <bits/stdc++.h>

#define i64 long long
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)

using namespace std;

const int N = 1e5 + 5, B = 4e2 + 5;

struct Operator {
    int l, r, x;
    Operator(int _l = 0, int _r = 0, int _x = 0) { l = _l; r = _r; x = _x; }
} op[N];

int n, m, totD, totB;
int L[B], R[B];
int a[N], bel[N], need[N], endTime[N], sum[N], d[N], bucket[N], cov[N];
vector<int> popID[N];

void workBlock(int b) {
    int cnt = 0, Max = 0;
    rep(i, L[b], R[b]) need[i] = a[i], Max = max(Max, need[i]); 
    
    auto workOP = [&](int id, int v) -> void {
        int ql = op[id].l, qr = op[id].r;

        if(ql <= L[b] && R[b] <= qr) cnt += v;
        else if(qr >= L[b] && ql <= R[b]) {
            Max = 0;
            rep(i, L[b], R[b]) {
                if(ql <= i && i <= qr) need[i] -= v;
                Max = max(Max, need[i]);
            }
        }
    };  

    for(int l = 1, r = 0; l <= m; l++) {
        while(r <= m && Max >= cnt) workOP(++r, 1);
        if(op[l].l <= L[b] && R[b] <= op[l].r) endTime[l] = max(endTime[l], r);
        workOP(l, -1);
    }

    totD = totB = 0;
    rep(i, 1, m) sum[i] = 0;
    rep(i, 1, m) {
        int ql = op[i].l, qr = op[i].r;

        if(ql <= L[b] && R[b] <= qr) {
            cov[++totB] = i;
            sum[totB] = sum[totB - 1] + 1;
        }
        else if(qr >= L[b] && ql <= R[b]) {
            cov[++totB] = i;
            d[++totD] = totB;
            sum[totB] = sum[totB - 1];
        }
    }

    cov[totB + 1] = m + 1;

    auto add = [&](int pos, int id, int v, int tar) -> void {
        int ql = op[cov[d[id]]].l, qr = op[cov[d[id]]].r;
        if(id != tar) cnt += v * (sum[d[id]] - sum[d[id - 1]]);
        if(ql <= pos && pos <= qr) cnt += v;
    };  

    auto del = [&](int pos, int id) -> void {
        int ql = op[cov[d[id]]].l, qr = op[cov[d[id]]].r;
        cnt -= (sum[d[id + 1]] - sum[d[id]]);
        if(ql <= pos && pos <= qr) cnt -= 1;
    };

    rep(i, L[b], R[b]) {
        cnt = 0; Max = a[i];
        for(int l = 1, r = 0; l <= totD;) {
            while(r < totD && Max >= cnt) add(i, ++r, 1, l);
            if(op[cov[d[l]]].l <= i && i <= op[cov[d[l]]].r) {
                if(Max >= cnt) {
                    int rest = Max - cnt + 1;
                    endTime[cov[d[l]]] = max(endTime[cov[d[l]]], cov[min(d[r] + rest, totB + 1)]);
                }
                else {
                    add(i, r--, -1, l);
                    int rest = Max - cnt + 1;
                    endTime[cov[d[l]]] = max(endTime[cov[d[l]]], cov[min(d[r] + rest, totB + 1)]);
                    add(i, ++r, 1, l);
                }
            }
            del(i, l++);
        }
    }
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];

    int B = sqrt(n), block = (n - 1) / B + 1;
    rep(i, 1, n) bel[i] = (i - 1) / B + 1;
    rep(i, 1, block) L[i] = (i - 1) * B + 1, R[i] = i * B;
    R[block] = n;

    rep(i, 1, m) cin >> op[i].l >> op[i].r >> op[i].x;

    rep(i, 1, block) workBlock(i);

    rep(i, 1, m) popID[endTime[i]].push_back(i);

    int ans = 0;
    rep(i, 1, m) {
        if(++bucket[op[i].x] == 1) ans++;
        for(auto id : popID[i]) if(--bucket[op[id].x] == 0) ans--;

        cout << ans << "\n";
    }

    return 0;
}