#include <bits/stdc++.h>

using i64 = long long;

template <typename Info, typename Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> s;
    std::vector<Tag> t;

    LazySegmentTree() = default;
    LazySegmentTree(int n_, const Info &v = Info{}) {
        init(n_, v);
    }
    template <typename T>
    LazySegmentTree(const std::vector<T> &v) {
        init(v);
    }
    void init(int n_, const Info &v = Info{}) {
        init(std::vector<Info>(n_, v));
    }
    template <typename T>
    void init(const std::vector<T> &v) {
        n = int(v.size());
        s.assign(4 << std::__lg(n), Info{});
        t.assign(4 << std::__lg(n), Tag{});
        auto build = [&](auto self, int u, int l, int r) -> void {
            if (r - l == 1) {
                s[u] = v[l];
                return;
            }
            int m = (l + r) / 2;
            self(self, u << 1, l, m);
            self(self, u << 1 | 1, m, r);
            pull(u);
        };
        build(build, 1, 0, n);
    }

    void pull(int u) {
        s[u] = s[u << 1] + s[u << 1 | 1];
    }
    void apply(int u, const Tag &v) {
        s[u].apply(v);
        t[u].apply(v);
    }
    void push(int u) {
        apply(u << 1, t[u]);
        apply(u << 1 | 1, t[u]);
        t[u] = Tag{};
    }

    void modify(int u, int l, int r, int p, const Info &v) {
        if (r - l == 1) {
            s[u] = v;
            return;
        }
        int m = (l + r) / 2;
        push(u);
        if (p < m) {
            modify(u << 1, l, m, p, v);
        } else {
            modify(u << 1 | 1, m, r, p, v);
        }
        pull(u);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }

    Info query(int u, int l, int r, int p) {
        if (r - l == 1) {
            return s[u];
        }
        int m = (l + r) / 2;
        push(u);
        if (p < m) {
            return query(u << 1, l, m, p);
        } else {
            return query(u << 1 | 1, m, r, p);
        }
    }
    Info query(int p) {
        return query(1, 0, n, p);
    }

    Info rangeQuery(int u, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql) {
            return Info{};
        }
        if (ql <= l && r <= qr) {
            return s[u];
        }
        int m = (l + r) / 2;
        push(u);
        return rangeQuery(u << 1, l, m, ql, qr) + rangeQuery(u << 1 | 1, m, r, ql, qr);
    }
    Info rangeQuery(int ql, int qr) {
        return rangeQuery(1, 0, n, ql, qr);
    }

    void rangeApply(int u, int l, int r, int ql, int qr, const Tag &v) {
        if (qr <= l || r <= ql) {
            return;
        }
        if (ql <= l && r <= qr) {
            apply(u, v);
            return;
        }
        int m = (l + r) / 2;
        push(u);
        rangeApply(u << 1, l, m, ql, qr, v);
        rangeApply(u << 1 | 1, m, r, ql, qr, v);
        pull(u);
    }
    void rangeApply(int ql, int qr, const Tag &v) {
        rangeApply(1, 0, n, ql, qr, v);
    }

    template <typename F>
    void applyFunction(int u, int l, int r, int p, F &&f) {
        if (r - l == 1) {
            f(s[u]);
            return;
        }
        int m = (l + r) / 2;
        push(u);
        if (p < m) {
            applyFunction(u << 1, l, m, p, f);
        } else {
            applyFunction(u << 1 | 1, m, r, p, f);
        }
        pull(u);
    }
    template <typename F>
    void applyFunction(int p, F &&f) {
        applyFunction(1, 0, n, p, f);
    }
};

constexpr int inf = 1e9;
constexpr int B = 64;

struct Tag {
    int v = 0;
    void apply(const Tag &b) {
        v += b.v;
    }
};

struct Info {
    int x = -inf;
    std::pair<int, int> y{inf, -1};
    void apply(const Tag &b) {
        x += b.v;
        y.first += b.v;
    }
};
Info operator+(const Info &a, const Info &b) {
    return Info{std::max(a.x, b.x), std::min(a.y, b.y)};
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, q;
    std::cin >> n >> q;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    std::vector<std::tuple<int, int, int>> qry;
    int m = 0;
    for (int i = 0; i < q; ++i) {
        int l, r, x;
        std::cin >> l >> r >> x;
        --l, --x;
        m = std::max(m, x + 1);
        qry.emplace_back(l, r, x);
    }

    std::vector<int> f(q);
    std::vector<std::vector<std::pair<int, int>>> que(n);
    std::vector<int> qhead(n);
    for (int bl = 0, br = 0; bl < n; bl = br) {
        br = std::min(bl + B, n);

        std::vector<int> val;
        int head = 0;
        LazySegmentTree<Info, Tag> seg(br - bl);
        for (int i = bl; i < br; ++i) {
            seg.modify(i - bl, Info{a[i], {inf, i}});
        }
        auto update = [&](int p, int x) {
            seg.applyFunction(p - bl, [&](Info &v) {
                v.x += x;
                v.y.first = qhead[p] == int(que[p].size()) ? inf : v.x + que[p][qhead[p]].second;
            });
        };
        for (int o = 0; o < q; ++o) {
            auto [l, r, x] = qry[o];
            if (br <= l || r <= bl) {
                continue;
            }
            l = std::max(l, bl);
            r = std::min(r, br);

            seg.rangeApply(l - bl, r - bl, Tag{-1});
            if (l == bl && r == br) {
                val.push_back(o);
            } else {
                for (int i = l; i < r; ++i) {
                    que[i].emplace_back(o, int(val.size()));
                    if (int(que[i].size()) == qhead[i] + 1) {
                        update(i, 0);
                    }
                }
            }

            while (seg.s[1].y.first - head < 0) {
                int p = seg.s[1].y.second;
                int t = que[p][qhead[p]++].first;
                f[t] = std::max(f[t], o);
                update(p, 1);
            }
            if (seg.s[1].x < 0) {
                int t = val[head++];
                f[t] = std::max(f[t], o);
                seg.apply(1, Tag{1});
            }
        }

        for (int i = head; i < int(val.size()); ++i) {
            f[val[i]] = q;
        }
    }
    for (int p = 0; p < n; ++p) {
        for (int i = qhead[p]; i < int(que[p].size()); ++i) {
            f[que[p][i].first] = q;
        }
    }

    std::vector<int> s(m, -1);
    std::vector<std::vector<int>> mdf(q + 1);
    int ans = 0;
    for (int i = 0; i < q; ++i) {
        auto [l, r, x] = qry[i];
        if (s[x] < f[i]) {
            if (s[x] < i) {
                ++ans;
            }
            s[x] = f[i];
            mdf[f[i]].push_back(x);
        }
        for (auto c : mdf[i]) {
            if (s[c] <= i) {
                --ans;
            }
        }
        std::cout << ans << "\n";
    }

    return 0;
}