#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
typedef long long ll;
using namespace std;
const int mxN = 200'005;
const int INF = 1'000'000'005;
struct fenwick{
    int n;
    int seg[mxN];
    void init(int _n){
        n = _n;
        for(int i=1;i<=n;i++) seg[i] = 0;
    }
    void upd(int pos, int val){
        for(int i=pos;i<=n;i+=(i&(-i))) seg[i] += val;
    }
    int pref(int pos){
        int res = 0;
        for(int i=pos;i>0;i-=(i&(-i))) res += seg[i];
        return res;
    }
    int solv(int s, int e){ return pref(e) - pref(s-1);}
};
int N, Q;
int A[mxN];
array <int, 3> qry[mxN];
int L[mxN], R[mxN];
int spsL[mxN][20], spsR[mxN][20];
int T[mxN];
vector <array<int, 5>> event;
fenwick F;
int ans[mxN];
void input(){
    cin >> N >> Q;
    for(int i=1;i<=N;i++) cin >> A[i];
    for(int i=1;i<=Q;i++) for(int j=0;j<3;j++) cin >> qry[i][j];
}
void makeLR(){
    vector <int> stk;
    for(int i=1;i<=N;i++){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        L[i] = (!stk.empty() ? stk.back() : 0);
        stk.push_back(i);
    }
    stk.clear();
    for(int i=N;i>=1;i--){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        R[i] = (!stk.empty() ? stk.back() : N+1);
        stk.push_back(i);
    }
}
void makeSparseTable(){
    for(int i=1;i<=N;i++) spsL[i][0] = L[i];
    for(int i=1;i<20;i++) for(int j=1;j<=N;j++) spsL[j][i] = spsL[spsL[j][i-1]][i-1];
    for(int i=1;i<=N;i++) spsR[i][0] = R[i];
    spsR[N+1][0] = N+1;
    for(int i=1;i<20;i++) for(int j=1;j<=N+1;j++) spsR[j][i] = spsR[spsR[j][i-1]][i-1];
}
void makeT(){
    vector <int> v;
    for(int i=1;i<=N;i++) v.push_back(i);
    sort(v.begin(), v.end(), [&](int a, int b){return A[a] < A[b];});
    for(int i=1;i<=N;i++) T[i] = 1;
    for(int x : v){
        if(L[x] == 0 || R[x] == N+1) T[x] = INF;
        if(L[x] != 0) T[L[x]] = max(T[L[x]], T[x] + 1);
        if(R[x] != N+1) T[R[x]] = max(T[R[x]], T[x] + 1);
    }
}
void makeEvent(){
    for(int i=1;i<=N;i++) event.push_back({T[i], 1, i, 0, 0});
    for(int i=1;i<=Q;i++){
        auto [l, r, t] = qry[i];
        event.push_back({t, 2, l, r, i});
    }
    sort(event.begin(), event.end());
}
void sweep(){
    F.init(N);
    for(int i=0;i<(int)event.size();i++){
        int t = event[i][0];
        if(event[i][1] == 1){
            int pos = event[i][2];
            F.upd(pos, 1);
        } else {
            int l = event[i][2], r = event[i][3], idx = event[i][4];
            int res = F.solv(l, r);
            int curL = l;
            if(T[l] <= t){
                res--;
                for(int j=19;j>=0;j--){
                    if(spsR[curL][j] <= r && T[spsR[curL][j]] <= t){
                        curL = spsR[curL][j];
                        res -= (1<<j);
                    }
                }
            }
            int curR = r;
            if(T[r] <= t){
                res--;
                for(int j=19;j>=0;j--){
                    if(spsL[curR][j] >= l && T[spsL[curR][j]] <= t){
                        curR = spsL[curR][j];
                        res -= (1<<j);
                    }
                }
            }
            if(curL == curR && T[curL] <= t) res++;
            ans[idx] = r - l + 1 - res;
        }
    }
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    input();
    makeLR();
    makeSparseTable();
    makeT();
    makeEvent();
    sweep();
    for(int i=1;i<=Q;i++) cout << ans[i] << '\n';
}