#include <bits/stdc++.h>
using namespace std;

// Structure to store differences applied to the Fenwick Trees
struct Event {
    int type; // 0 for Vertical, 1 for Diagonal
    int pos;
    long long val;
};

// Structure for offline prefix queries
struct Query {
    int X;
    int sign;
    int id;
};

// Binary Indexed Tree designed using __int128_t to completely prevent large sum overflows
struct BIT {
    int n;
    vector<__int128_t> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {}
    
    void add(int i, __int128_t delta) {
        if (i <= 0) return;
        for (; i <= n; i += i & -i) tree[i] += delta;
    }
    
    __int128_t query(int i) {
        if (i <= 0) return 0;
        i = min(i, n);
        __int128_t sum = 0;
        for (; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
};

// Safely queues the boundary events ensuring they are added within valid time T bounds
void add_seg(int type, int pos, long long V, long long Ts, long long Te, vector<vector<Event>>& evs, int N) {
    Ts = max(0LL, Ts);
    Te = min((long long)N, Te);
    if (Ts <= Te) {
        evs[Ts].push_back({type, pos, V});
        if (Te + 1 <= N) {
            evs[Te + 1].push_back({type, pos, -V});
        }
    }
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, Q;
    if (!(cin >> N >> Q)) return 0;
    
    vector<long long> S(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> S[i];
    }

    // P[i]: largest j < i such that S[j] > S[i]
    vector<int> P(N + 1);
    vector<int> st;
    for (int i = 1; i <= N; ++i) {
        while (!st.empty() && S[st.back()] <= S[i]) st.pop_back();
        P[i] = st.empty() ? -1e9 : st.back();
        st.push_back(i);
    }
    
    // N_idx[i]: smallest j > i such that S[j] >= S[i]
    vector<int> N_idx(N + 1);
    st.clear();
    for (int i = N; i >= 1; --i) {
        while (!st.empty() && S[st.back()] < S[i]) st.pop_back();
        N_idx[i] = st.empty() ? N + 1 : st.back();
        st.push_back(i);
    }

    vector<vector<Event>> evs(N + 2);
    for (int i = 1; i <= N; ++i) {
        long long p = P[i];
        long long n = N_idx[i];
        long long v = S[i];

        // Generate the 4 boundary segments for the geometric region mapped to this S[i]
        // Pos 1 (Vertical):  Starts immediately, stops when it hits diagonal overlap
        add_seg(0, i, v, 0, i - p - 1, evs, N);
        // Pos 2 (Diagonal):  Takes over after vertical overlap finishes
        add_seg(1, p + 1, v, i - p, n - p - 2, evs, N);
        
        // Neg 1 (Diagonal):  Maintains bounded window sliding rightward
        add_seg(1, i + 1, -v, 0, n - i - 1, evs, N);
        // Neg 2 (Vertical):  Cutoff segment if a greater/equal element takes rightward dominance
        add_seg(0, n, -v, n - i, n - p - 2, evs, N);
    }

    // Subdividing range queries into prefix summations
    vector<vector<Query>> queries(N + 2);
    for (int j = 0; j < Q; ++j) {
        int T, L, R;
        cin >> T >> L >> R;
        queries[T].push_back({R, 1, j});
        queries[T].push_back({L - 1, -1, j});
    }

    BIT bit_V(N + 2), bit_yV(N + 2);
    BIT bit_D(N + 2), bit_CD(N + 2);
    vector<long long> ans(Q, 0);

    // Sweep-line passing over time intervals T
    for (int T = 0; T <= N; ++T) {
        for (auto& ev : evs[T]) {
            if (ev.type == 0) {
                bit_V.add(ev.pos, ev.val);
                bit_yV.add(ev.pos, (__int128_t)ev.pos * ev.val);
            } else {
                bit_D.add(ev.pos, ev.val);
                bit_CD.add(ev.pos, (__int128_t)ev.pos * ev.val);
            }
        }
        
        // Answer all sub-queries offline at the current T 
        for (auto& q : queries[T]) {
            if (q.X == 0) continue;
            long long X = q.X;
            __int128_t res = 0;

            // Prefix formulas factoring (X + 1) * V - y * V offsets
            __int128_t sum_V = bit_V.query(X);
            __int128_t sum_yV = bit_yV.query(X);
            res += (X + 1) * sum_V - sum_yV;

            if (X - T >= 1) {
                __int128_t sum_D = bit_D.query(X - T);
                __int128_t sum_CD = bit_CD.query(X - T);
                res += (X + 1 - T) * sum_D - sum_CD;
            }

            if (q.sign == 1) ans[q.id] += (long long)res;
            else ans[q.id] -= (long long)res;
        }
    }

    for (int j = 0; j < Q; ++j) {
        cout << ans[j] << "\n";
    }

    return 0;
}