#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int N = 400010;

struct Fenwick {

  ull fw[N * 2];

  void ch(int k, ull x) {
    for (; k < N; k += k & -k) fw[k] += x;
  }

  ull qry(int k) {
    ull ret = 0;
    for (; k; k &= k - 1) ret += fw[k];
    return ret;
  }

};

struct R {

  Fenwick fw0, fw1;

  void ch(int k, ull x) {
    fw0.ch(k, (k - 1) * x);
    fw1.ch(k, x);
  }

  ull qry(int k) {
    return fw1.qry(k) * k - fw0.qry(k);
  }

} rect, tri;

int n, q;
int sl[N * 2], sr[N * 2];
ull ans[N];
vector<tuple<int, int, int>> query[N];
vector<pair<int, ull>> modifyR[N * 2], modifyT[N * 2];

pair<int, int> s[N];

ull gans(int t, int k) {
  return rect.qry(k) + tri.qry(t + k);
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i].first;
    s[i].second = i;
  }
  for (int i = 1; i <= q; ++i) {
    int t, l, r;
    cin >> t >> l >> r;
    query[t].emplace_back(l + n - t, r + n - t, i);
  }
  sort(s + 1, s + n + 1);
  sl[1] = sl[n] = 1;
  sr[1] = sr[n] = n;
  for (int i = 1; i <= n; ++i) {
    int j = s[i].second + n;
    int vl = j, vr = j;
    if (sl[j - 1])
      vl = sl[j - 1];
    if (sr[j + 1])
      vr = sr[j + 1];
    sl[vl] = sl[vr] = vl;
    sr[vl] = sr[vr] = vr;


    modifyT[0].emplace_back(j, s[i].first);
    modifyT[j - vl + 1].emplace_back(j, -s[i].first);
    modifyR[j - vl + 1].emplace_back(vl, s[i].first);
    modifyR[vr - vl + 1].emplace_back(vl, -s[i].first);

    modifyR[0].emplace_back(j + 1, -s[i].first);
    modifyR[vr - j + 1].emplace_back(j + 1, s[i].first);
    modifyT[vr - j + 1].emplace_back(vr + 1, -s[i].first);
    modifyT[vr - vl + 1].emplace_back(vr + 1, s[i].first);
  }

  for (int t = 0; t <= n; ++t) {
    for (const auto& pr : modifyR[t])
      rect.ch(pr.first, pr.second);
    for (const auto& pr : modifyT[t])
      tri.ch(pr.first, pr.second);
    for (const auto &tup : query[t]) {
      int l, r, id;
      tie(l, r, id) = tup;

      ans[id] = gans(t, r) - gans(t, l - 1);
    }
  }

  for (int i = 1; i <= q; ++i)
    cout << ans[i] << '\n';

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}