#include struct FastI { char buf[1000000]; char *ptr = buf, *end; void read_() { end = (ptr = buf) + fread(buf, 1, sizeof(buf) - 1, stdin); } FastI () { read_(); } void inc() { if (++ptr == end) read_(); } template value_t read() { bool neg = false; value_t res = 0; while ((*ptr < '0' || *ptr > '9') && *ptr != '-') inc(); if (*ptr == '-') neg = true, inc(); while (*ptr >= '0' && *ptr <= '9') res = res * 10 + *ptr - '0', inc(); return neg ? -res : res; } } fasti; #define ri fasti.read #define rs64 fasti.read struct FastO { char buf[1000000]; char *ptr = buf; void write_() { fwrite(buf, 1, ptr - buf, stdout); ptr = buf; } ~FastO () { write_(); } void print(char c) { *ptr = c; if (++ptr == std::end(buf)) write_(); } void print(const std::string &s) { for (auto c : s) print(c); } template auto print(str_t s) -> decltype(std::string(s), void()) { print(std::string(s)); } template typename std::enable_if_t::value> print(value_t val) { static char tmp_buf[32]; if (val < 0) print('-'), val = -val; char *head = std::end(tmp_buf); if (val == 0) *--head = '0'; else while (val) *--head = '0' + val % 10, val /= 10; int size = std::end(tmp_buf) - head; if (std::end(buf) - ptr <= size) write_(); memcpy(ptr, head, size); ptr += size; } template void print(A a, B... b) { print(a); print(b...); } template void println(A... a) { print(a..., '\n'); } } fasto; #define print fasto.print #define println fasto.println template struct segtree { using value_t = decltype(monoid_t::unit()); static_assert(std::is_same::value || std::is_same::value); value_t unit() { return monoid_t::unit(); } int n_, n; std::vector data; int ceil_power2(int x) { int i = 1; while (i < x) i <<= 1; return i; } segtree (int n_) : n_(n_), n(ceil_power2(n_)), data(n << 1, unit()) {} template segtree (itr_t begin, itr_t end) : segtree(end - begin) { std::copy(begin, end, data.begin() + n); for (int i = n; --i; ) fetch(i); } template segtree (const std::vector &a) : segtree(a.begin(), a.end()) {} void fetch(int i) { data[i] = monoid_t::op(data[i << 1], data[i << 1 | 1]); } void assign(int i, const value_t &val) { for (data[i += n] = val; i >>= 1; ) fetch(i); } value_t operator [] (int i) { return data[i + n]; } void apply(int i, const value_t &val) { for (i += n; i; i >>= 1) data[i] = monoid_t::op(data[i], val); } value_t aggregate(int l, int r) { value_t left = unit(), right = unit(); for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (r & 1) right = monoid_t::op(data[--r], right); if (l & 1) left = monoid_t::op(left, data[l++]); } return monoid_t::op(left, right); } template int lower_bound(const lambda_t &is_lower) { if (is_lower(data[1])) return n_ + 1; if (!is_lower(unit())) return 0; value_t cur = unit(); int res = 0; for (int size = n, node = 1; size > 1; size >>= 1) { value_t next = monoid_t::op(cur, data[node <<= 1]); if (is_lower(next)) cur = next, res += size >> 1, node++; } return res + 1; } int lower_bound(const value_t &val) { return lower_bound([val] (value_t x) { return x < val; }); } }; template struct add { static T unit() { return 0; } static T op(T a, T b) { return a + b; } }; int main() { int n = ri(); int q = ri(); std::vector a(n); std::vector > p(n); for (int i = 0; i < n; i++) { a[i] = ri(); p[i] = {a[i], i}; } std::sort(p.begin(), p.end()); int head = n - 1; struct Query { int l; int r; int x; int id; }; Query qs[q]; for (auto &i : qs) i.l = ri() - 1, i.r = ri(), i.x = ri(); for (int i = 0; i < q; i++) qs[i].id = i; std::sort(qs, qs + q, [] (auto &i, auto &j) { return i.x > j.x; }); segtree > tree0(n); segtree > tree1(a); std::vector res(q); for (auto &i : qs) { while (head >= 0 && p[head].first >= i.x) { tree0.apply(p[head].second, 1); tree1.apply(p[head].second, -a[p[head].second]); head--; } res[i.id] = (int64_t) i.x * tree0.aggregate(i.l, i.r) + tree1.aggregate(i.l, i.r); } for (auto i : res) println(i); return 0; }