#include #include using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < (int)(n); i++) void solve() { ll n, q; cin >> n >> q; vector a(n); rep(i, n) cin >> a[i]; vector> xlrs(q); rep(qi, q) { ll l, r, x; cin >> l >> r >> x; xlrs[qi] = {x, l, r, qi}; } sort(xlrs.begin(), xlrs.end()); vector> que(n); rep(i, n) que[i] = {a[i], i}; sort(que.rbegin(), que.rend()); atcoder::fenwick_tree bit1(n), bit2(n); rep(i, n) bit1.add(i, a[i]), bit2.add(i, -1); vector ans(q); for (const auto &[x, l, r, qi] : xlrs) { while (!que.empty() && que.back().first < x) { auto [v, i] = que.back(); que.pop_back(); bit1.add(i, -v * 2), bit2.add(i, 2); } ans[qi] = bit1.sum(l - 1, r) + x * bit2.sum(l - 1, r); } rep(qi, q) cout << ans[qi] << '\n'; } int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); int T = 1; for (int t = 0; t < T; t++) { solve(); } return 0; }