#include<bits/stdc++.h>
using namespace std;
const int MN = 5e5 + 5;
using ll = long long;
int n, m, a[MN];
int num[MN << 1], N;
struct que{
    int x, l, r;
}q[MN];
namespace zkw{
    struct Node{
        ll v;
        int num;
        int ls, rs;
    }T[MN * 20];
    int N, rt[MN];
    void add(int& x, int y, int l, int r, int pos) {
        if(!x) x = ++N;
        
        if(l == r) {
            T[x] = T[y];
            T[x].num++;
            T[x].v += num[pos];
            return;
        }
        int mid = l + r >> 1;
        if(pos <= mid)
            add(T[x].ls, T[y].ls, l, mid, pos),
            T[x].rs = T[y].rs;
        else
            add(T[x].rs, T[y].rs, mid + 1, r, pos),
            T[x].ls = T[y].ls;
        T[x].num = T[T[x].ls].num + T[T[x].rs].num;
        T[x].v = T[T[x].ls].v + T[T[x].rs].v;
    }
    void add2(int& x, int l, int r, int pos) {
        if(!x) x = ++N;
        
        if(l == r) {
            T[x].num++;
            T[x].v += num[pos];
            return;
        }
        int mid = l + r >> 1;
        if(pos <= mid)
            add2(T[x].ls, l, mid, pos);
        else
            add2(T[x].rs, mid + 1, r, pos);
        T[x].num = T[T[x].ls].num + T[T[x].rs].num;
        T[x].v = T[T[x].ls].v + T[T[x].rs].v;
    }
    ll query(int x, int y, int l, int r, int k) {
        if(l == r) {
            return (ll)k * num[l];
        }
        int mid = l + r >> 1;
        if(k <= T[T[x].rs].num + T[T[y].rs].num)
            return query(T[x].rs, T[y].rs, mid + 1, r, k);
        return T[T[x].rs].v + T[T[y].rs].v + query(T[x].ls, T[y].ls, l, mid, k - (T[T[x].rs].num + T[T[y].rs].num));
    }
}
using zkw::rt;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        num[i] = a[i];
    }
    N = n + m;
    for(int i = 1; i <= m; i++) {
        cin >> q[i].x >> q[i].l >> q[i].r;
        num[i + n] = q[i].x;
    }
    sort(num + 1, num + 1 + N);
    N = unique(num + 1, num + 1 + N) - num - 1;
    for(int i = 1; i <= n; i++)
        zkw::add(rt[i], rt[i - 1], 1, N, lower_bound(num + 1, num + 1 + N, a[i]) - num);
    for(int i = 1; i <= m; i++) {
        auto [x, l, r] = q[i];
        zkw::add2(rt[n + 1], 1, N, lower_bound(num + 1, num + 1 + N, x) - num);
        // cerr << zkw::query(rt[1], rt[n + 1], 1, N, 1) << "\n";
        // cerr << zkw::T[rt[1]].v << "\n";
        cout << zkw::query(rt[r], rt[n + 1], 1, N, r) - zkw::query(rt[l - 1], rt[n + 1], 1, N, l - 1) << "\n";
    }
}
/*
6 8
1 6 1 3 5 4
2 3 6
3 3 4
2 4 4
6 3 5
4 1 1
4 2 3
2 4 6
1 3 3

6 1
1 6 1 3 5 4
2 1 6
*/