#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 2e5 + 5;

int n, q;
int a[kMaxN], pre[kMaxN], nxt[kMaxN];

void prework() {
  static int stk[kMaxN];
  int top = 0;
  std::fill_n(nxt + 1, n, 1e9);
  stk[0] = -1e9;
  for (int i = 1; i <= n; ++i) {
    for (; top && a[stk[top]] < a[i]; nxt[stk[top--]] = i) {}
    pre[i] = stk[top];
    stk[++top] = i;
  }
}
int solve(int R, int t) {
  int ans = 0;
  for (int i = 1; i <= R; ++i) {
    int l = std::max(i, pre[i] + t + 1), r = std::min({i + t, nxt[i] - 1, R});
    if (l <= r) ans += a[i] * (r - l + 1);
  }
  return ans;
}
int S(int i, int t) {
  int ret = 0;
  for (int j = std::max<int>(i - t, 1); j <= i; ++j)
    ret = std::max(ret, a[j]);
  return ret;
}
void dickdreamer() {
  std::cin >> n >> q;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  prework();
  for (int i = 1; i <= q; ++i) {
    int t, l, r;
    std::cin >> t >> l >> r;
    std::cout << solve(r, t) - solve(l - 1, t) << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  while (T--) dickdreamer();
  return 0;
}