C

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

struct Fenwick {
  int size;
  vector<long long> bit;

  Fenwick() {}

  explicit Fenwick(int n) : size(n), bit(n + 1) {}

  void update(int i, long long value) {
    for (++i; i <= size; i += i & -i) {
      bit[i] += value;
    }
  }

  long long query(int r) {
    long long result = 0;
    for (; r > 0; r -= r & -r) {
      result += bit[r];
    }
    return result;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int &value : a) {
    cin >> value;
  }
  vector<int> jl(n), jr(n);
  for (int i = 0; i < n; i++) {
    jl[i] = i - 1;
    while (jl[i] != -1 && a[jl[i]] >= a[i]) {
      jl[i] = jl[jl[i]];
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    jr[i] = i + 1;
    while (jr[i] != n && a[jr[i]] > a[i]) {
      jr[i] = jr[jr[i]];
    }
  }
  vector<array<int, 4>> queries;
  for (int i = 0; i < q; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    --l;
    queries.push_back({l, k, +1, i});
    queries.push_back({r - k + 1, k, -1, i});
  }
  vector<long long> result(q);
  // auto Query = [&](int start, int k) -> long long {
  //   long long result = 0;
  //   for (int i = 0; i < n; i++) {
  //     int coeff = max(0, min(i + 1, jr[i] - k + 1) - max({jl[i] + 1, start, i + 1 - k}));
  //     int my_coeff = 0;
  //     if (k <= jr[i] - i) {
  //       if (start <= jl[i] + 1 && k >= i - jl[i]) {
  //         my_coeff = i - jl[i];
  //       }
  //       if (start > jl[i] + 1 && start + k >= i + 1 && start <= i + 1) {
  //         my_coeff = i + 1 - start;
  //       }
  //       if (k < i - jl[i] && start + k < i + 1) {
  //         my_coeff = k;
  //       }
  //     } else {
  //       if (start <= jl[i] + 1 && k >= i - jl[i] && k <= jr[i] - jl[i]) {
  //         my_coeff = jr[i] - jl[i] - k;
  //       }
  //       // if (start > jl[i] + 1 && start + k >= i + 1 && k <= jr[i] + 1 - start) {
  //       //   my_coeff = (jr[i] - k + 1) - start;
  //       // }
  //       if (k < i - jl[i] && start + k < i + 1) {
  //         my_coeff = jr[i] - i;
  //       }
  //     }
  //     assert(my_coeff >= 0);
  //     // assert(my_coeff == coeff);
  //     result += 1LL * my_coeff * a[i];
  //   }
  //   return result;
  // };
  // vector<long long> result1(q);
  // for (auto &[start, k, sign, ind] : queries) {
  //   result1[ind] += sign * Query(start, k);
  // }
  // Case 1.1: k >= i - jl[i] && k <= jr[i] - i && start <= jl[i] + 1
  // Add (i - jl[i]) * a[i]
  {
    using Event = tuple<int, int, int, int, long long>;
    vector<Event> events;
    for (int i = 0; i < n; i++) {
      int l = i - jl[i], r = jr[i] - i;
      if (l <= r) {
        events.push_back({jl[i] + 1, 1, l, r, 1LL * (i - jl[i]) * a[i]});
      }
    }
    for (int i = 0; i < queries.size(); i++) {
      events.push_back({queries[i][0], 2, queries[i][1], queries[i][2], queries[i][3]});
    }
    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
      auto &[xa, ta, y1a, y2a, valuea] = a;
      auto &[xb, tb, y1b, y2b, valueb] = b;
      return xa != xb ? xa > xb : ta < tb;
    });
    Fenwick bit(n + 1);
    for (auto &[x, t, y1, y2, value] : events) {
      if (t == 1) {
        bit.update(y1, +value);
        bit.update(y2 + 1, -value);
      } else {
        result[value] += y2 * bit.query(y1 + 1);
      }
    }
  }
  // Case 1.2. start >= jl[i] + 2 && start + k >= i + 1 && start <= i + 1 && k <= jr[i] - i
  // Add (i + 1 - start) * a[i] = (i + 1) * a[i] - start * a[i]
  {
    using Event = tuple<int, int, int, int, int, long long>;
    vector<Event> events;
    for (int i = 0; i < n; i++) {
      int l = jl[i] + 2, r = i + 1;
      if (l <= r) {
        events.push_back({jr[i] - i, -(i + 1), 1, l, r, i});
      }
    }
    vector<long long> mlt1(queries.size()), mlt2(queries.size());
    for (int i = 0; i < queries.size(); i++) {
      events.push_back({queries[i][1], -(queries[i][0] + queries[i][1]), 2, queries[i][0], queries[i][2], i});
    }
    auto CmpLocal = [&](const Event& a, const Event& b) {
      auto &[xa, ya, ta, z1a, z2a, inda] = a;
      auto &[xb, yb, tb, z1b, z2b, indb] = b;
      return ya != yb ? ya > yb : ta < tb;
    };
    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
      auto &[xa, ya, ta, z1a, z2a, inda] = a;
      auto &[xb, yb, tb, z1b, z2b, indb] = b;
      return xa != xb ? xa > xb : ta < tb;
    });
    Fenwick bit1(n + 1), bit2(n + 1);
    vector<Event> evs;
    auto CDQ = [&](auto&& self, int low, int high) -> void {
      if (high - low == 1) {
        return;
      }
      int mid = (low + high) / 2;
      self(self, low, mid);
      self(self, mid, high);
      for (int i = low; i < mid; i++) {
        if (get<2>(events[i]) == 1) {
          evs.push_back(events[i]);
        }
      }
      int delta = evs.size();
      for (int i = mid; i < high; i++) {
        if (get<2>(events[i]) == 2) {
          evs.push_back(events[i]);
        }
      }
      inplace_merge(evs.begin(), evs.begin() + delta, evs.end(), CmpLocal);
      for (auto &e : evs) {
        auto [x, y, t, z1, z2, ind] = e;
        if (t == 1) {
          long long value1 = 1LL * (ind + 1) * a[ind], value2 = a[ind];
          bit1.update(z1, +value1);
          bit1.update(z2 + 1, -value1);
          bit2.update(z1, +value2);
          bit2.update(z2 + 1, -value2);
        } else {
          mlt1[ind] += z2 * bit1.query(z1 + 1);
          mlt2[ind] += z2 * bit2.query(z1 + 1);
        }
      }
      inplace_merge(events.begin() + low, events.begin() + mid, events.begin() + high, CmpLocal);
      for (auto &e : evs) {
        auto [x, y, t, z1, z2, ind] = e;
        if (t == 1) {
          long long value1 = 1LL * (ind + 1) * a[ind], value2 = a[ind];
          bit1.update(z1, -value1);
          bit1.update(z2 + 1, +value1);
          bit2.update(z1, -value2);
          bit2.update(z2 + 1, +value2);
        }
      }
      evs.clear();
    };
    CDQ(CDQ, 0, events.size());
    for (int i = 0; i < queries.size(); i++) {
      result[i / 2] += mlt1[i] - queries[i][0] * mlt2[i];
    }
  }
  // Case 1.3. k <= i - jl[i] - 1 && start + k <= i && k <= jr[i] - i
  // Add k * a[i]
  {
    using Event = tuple<int, int, int, int, long long>;
    vector<Event> events;
    for (int i = 0; i < n; i++) {
      int l = 0, r = min(i - jl[i] - 1, jr[i] - i);
      if (l <= r) {
        events.push_back({i, 1, l, r, a[i]});
      }
    }
    for (int i = 0; i < queries.size(); i++) {
      events.push_back({queries[i][0] + queries[i][1], 2, queries[i][1], queries[i][2], queries[i][3]});
    }
    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
      auto &[xa, ta, y1a, y2a, valuea] = a;
      auto &[xb, tb, y1b, y2b, valueb] = b;
      return xa != xb ? xa > xb : ta < tb;
    });
    Fenwick bit(n + 1);
    vector<long long> mlt(q);
    for (auto &[x, t, y1, y2, value] : events) {
      if (t == 1) {
        bit.update(y1, +value);
        bit.update(y2 + 1, -value);
      } else {
        mlt[value] += y2 * bit.query(y1 + 1);
      }
    }
    for (int i = 0; i < q; i++) {
      result[i] += mlt[i] * queries[i * 2][1];
    }
  }
  // Case 2.1: start <= jl[i] + 1 && k >= i - jl[i] && k <= jr[i] - jl[i] && k > jr[i] - i
  // (jr[i] - jl[i] - k) * a[i]
  // (jr[i] - jl[i]) * a[i]
  // -k * a[i]
  /*
        if (start <= jl[i] + 1 && k >= i - jl[i] && k <= jr[i] - jl[i]) {
          my_coeff = jr[i] - jl[i] - k;
        }
  */
  {
    using Event = tuple<int, int, int, int, long long>;
    vector<Event> events;
    for (int i = 0; i < n; i++) {
      int l = max(i - jl[i], jr[i] - i + 1), r = jr[i] - jl[i];
      if (l <= r) {
        events.push_back({jl[i] + 1, 1, l, r, i});
      }
    }
    for (int i = 0; i < queries.size(); i++) {
      events.push_back({queries[i][0], 2, queries[i][1], queries[i][2], queries[i][3]});
    }
    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
      auto &[xa, ta, y1a, y2a, valuea] = a;
      auto &[xb, tb, y1b, y2b, valueb] = b;
      return xa != xb ? xa > xb : ta < tb;
    });
    Fenwick bit1(n + 1), bit2(n + 1);
    vector<long long> mlt1(q), mlt2(q);
    for (auto &[x, t, y1, y2, value] : events) {
      if (t == 1) {
        long long value1 = 1LL * (jr[value] - jl[value]) * a[value], value2 = a[value];
        bit1.update(y1, +value1);
        bit1.update(y2 + 1, -value1);
        bit2.update(y1, +value2);
        bit2.update(y2 + 1, -value2);
      } else {
        mlt1[value] += y2 * bit1.query(y1 + 1);
        mlt2[value] += y2 * bit2.query(y1 + 1);
      }
    }
    for (int i = 0; i < q; i++) {
      result[i] += mlt1[i] - mlt2[i] * queries[i * 2][1];
    }
  }
  // Case 2.2: start > jl[i] + 1 && start + k >= i + 1 && start + k <= jr[i] + 1 && k > jr[i] - i
  // Add (jr[i] - k + 1 - start) * a[i] = (jr[i] + 1) * a[i] - (k + start) * a[i]
    {
    using Event = tuple<int, int, int, int, int, long long>;
    vector<Event> events;
    for (int i = 0; i < n; i++) {
      int l = i + 1, r = jr[i] + 1;
      if (l <= r) {
        events.push_back({-(jl[i] + 2), -(jr[i] - i + 1), 1, l, r, i});
      }
    }
    vector<long long> mlt1(queries.size()), mlt2(queries.size());
    for (int i = 0; i < queries.size(); i++) {
      events.push_back({-queries[i][0], -queries[i][1], 2, queries[i][0] + queries[i][1], queries[i][2], i});
    }
    auto CmpLocal = [&](const Event& a, const Event& b) {
      auto &[xa, ya, ta, z1a, z2a, inda] = a;
      auto &[xb, yb, tb, z1b, z2b, indb] = b;
      return ya != yb ? ya > yb : ta < tb;
    };
    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
      auto &[xa, ya, ta, z1a, z2a, inda] = a;
      auto &[xb, yb, tb, z1b, z2b, indb] = b;
      return xa != xb ? xa > xb : ta < tb;
    });
    Fenwick bit1(2 * n + 1), bit2(2 * n + 1);
    vector<Event> evs;
    auto CDQ = [&](auto&& self, int low, int high) -> void {
      if (high - low == 1) {
        return;
      }
      int mid = (low + high) / 2;
      self(self, low, mid);
      self(self, mid, high);
      for (int i = low; i < mid; i++) {
        if (get<2>(events[i]) == 1) {
          evs.push_back(events[i]);
        }
      }
      int delta = evs.size();
      for (int i = mid; i < high; i++) {
        if (get<2>(events[i]) == 2) {
          evs.push_back(events[i]);
        }
      }
      inplace_merge(evs.begin(), evs.begin() + delta, evs.end(), CmpLocal);
      for (auto &e : evs) {
        auto &[x, y, t, z1, z2, ind] = e;
        if (t == 1) {
          long long value1 = 1LL * (jr[ind] + 1) * a[ind], value2 = a[ind];
          bit1.update(z1, +value1);
          bit1.update(z2 + 1, -value1);
          bit2.update(z1, +value2);
          bit2.update(z2 + 1, -value2);
        } else {
          mlt1[ind] += z2 * bit1.query(z1 + 1);
          mlt2[ind] += z2 * bit2.query(z1 + 1);
        }
      }
      inplace_merge(events.begin() + low, events.begin() + mid, events.begin() + high, CmpLocal);
      for (auto &e : evs) {
        auto &[x, y, t, z1, z2, ind] = e;
        if (t == 1) {
          long long value1 = 1LL * (jr[ind] + 1) * a[ind], value2 = a[ind];
          bit1.update(z1, -value1);
          bit1.update(z2 + 1, +value1);
          bit2.update(z1, -value2);
          bit2.update(z2 + 1, +value2);
        }
      }
      evs.clear();
    };
    CDQ(CDQ, 0, events.size());
    for (int i = 0; i < queries.size(); i++) {
      result[i / 2] += mlt1[i] - (queries[i][0] + queries[i][1]) * mlt2[i];
    }
  }
  // Case 2.3: i + 1 - k > jl[i] + 1 && i + 1 - k > start
  // <=> k < i - jl[i] && start + k < i + 1 <=> start + k <= i && k > jr[i] - i
  // Add (jr[i] - i) * a[i]
  {
    using Event = tuple<int, int, int, int, long long>;
    vector<Event> events;
    for (int i = 0; i < n; i++) {
      int l = jr[i] - i + 1, r = i - jl[i] - 1;
      if (l <= r) {
        events.push_back({i, 1, l, r, 1LL * (jr[i] - i) * a[i]});
      }
    }
    for (int i = 0; i < queries.size(); i++) {
      events.push_back({queries[i][0] + queries[i][1], 2, queries[i][1], queries[i][2], queries[i][3]});
    }
    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
      auto &[xa, ta, y1a, y2a, valuea] = a;
      auto &[xb, tb, y1b, y2b, valueb] = b;
      return xa != xb ? xa > xb : ta < tb;
    });
    Fenwick bit(n + 1);
    for (auto &[x, t, y1, y2, value] : events) {
      if (t == 1) {
        bit.update(y1, +value);
        bit.update(y2 + 1, -value);
      } else {
        result[value] += y2 * bit.query(y1 + 1);
      }
    }
  }
  for (auto value : result) {
    cout << value << "\n";
  }
}