fsecv

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("fsecv.in");
ofstream fout("fsecv.out");
#include <bits/stdc++.h>
#define endl '\n'
#endif

const int NMAX  = 1e5+2;

struct Query {
    int l, r, k, idx;
};

int n, q;
int a[NMAX];
int *p[NMAX];
int bucket[NMAX];
int sq;
Query qs[NMAX];
int ap[NMAX];
int ans[NMAX];
int cnt[NMAX];

bool cmp(const int *a, const int *b) {
    return *a < *b;
}

bool cmp2(const Query &a, const Query &b) {
    if (bucket[a.l] == bucket[b.l]) return a.r < b.r;
    return a.l < b.l;
}

void read() {
    fin >> n >> q;
    for (int i = 1; i <= n; i++) {
        fin >> a[i];
    }
    for (int i = 1; i <= q; i++) {
        fin >> qs[i].l >> qs[i].r >> qs[i].k;
    }
}

void precalc() {
    sq = sqrt(n);
    for (int i = 1; i <= n; i++)
        bucket[i] = (i - 1) / sq + 1;

    for (int i = 1; i <= n; i++)
        p[i] = &a[i];
    sort(p + 1, p + n + 1, cmp);

    int val = 0;
    for (int i = 1; i <= n; i++) {
        int v = *p[i];
        *p[i] = val;
        if (i != n && v != *p[i + 1]) val++;
    }

    for (int i = 1; i <= q; i++)
        qs[i].idx = i;
    sort(qs + 1, qs + q + 1, cmp2);
}

void solve() {
    int l = 1, r = 1;
    ap[a[1]] = 1;
    cnt[1] = 1;
    for (int i = 1; i <= q; i++) {
        while (l < qs[i].l) {
            cnt[ap[a[l]]]--;
            cnt[ap[a[l]] - 1]++;
            ap[a[l++]]--;
        }
        while (qs[i].r < r) {
            cnt[ap[a[r]]]--;
            cnt[ap[a[r]] - 1]++;
            ap[a[r--]]--;
        }
        while (qs[i].l < l) {
            cnt[ap[a[l - 1]]]--;
            ap[a[--l]]++;
            cnt[ap[a[l]]]++;
        }
        while (r < qs[i].r) {
            cnt[ap[a[r + 1]]]--;
            ap[a[++r]]++;
            cnt[ap[a[r]]]++;
        }
        ans[qs[i].idx] = cnt[qs[i].k];
    }
    for (int i = 1; i <= q; i++)
        fout << ans[i] << endl;
}

int main() {
    read();
    precalc();
    solve();
    return 0;
}