#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

vector<int> a, b;

template<class T>
struct segtree{ // [l,r)
    int n;
    vector<vector<T>> sum, all;
    segtree(int sz){
        n = (1 << ((int)(log2(sz - 1)) + 1));
        sum.resize(n + n);
        all.resize(n + n);
    }
    void build(int root, int l, int r){
        if (l >= r) return;
        if (l >= a.size()) return;
        if (l + 1 == r){
            all[root].push_back(a[l]);
            sum[root].push_back(a[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(root<<1, l, mid);
        build(root<<1|1, mid, r);
        all[root].resize(all[root<<1].size() + all[root<<1|1].size());
        merge(all[root<<1].begin(), all[root<<1].end(), all[root<<1|1].begin(), all[root<<1|1].end(), all[root].begin());
        sum[root].resize(all[root<<1].size() + all[root<<1|1].size());
        for (int i = 0; i < sum[root].size(); i++)
            sum[root][i] = all[root][i] + (i == 0 ? 0 : sum[root][i - 1]);
    }
    int find_cnt(int x, int y, T val, int root, int l, int r){
        if (r <= x || l >= y) return 0;
        if (l >= x && r <= y){
            int p = (int)(upper_bound(all[root].begin(), all[root].end(), val) - all[root].begin());
            return p;
        }
        int mid = (l + r) >> 1;
        return find_cnt(x, y, val, root<<1, l, mid) + find_cnt(x, y, val, root<<1|1, mid, r);
    }
    int find_cnt(int x, int y, T val){
        return find_cnt(x, y, val, 1, 0, n);
    }
    T find_sum(int x, int y, T val, int root, int l, int r){
        if (r <= x || l >= y) return 0;
        if (l >= x && r <= y){
            int p = (int)(upper_bound(all[root].begin(), all[root].end(), val) - all[root].begin());
            return (p == 0 ? 0 : sum[root][p - 1]);
        }
        int mid = (l + r) >> 1;
        return find_sum(x, y, val, root<<1, l, mid) + find_sum(x, y, val, root<<1|1, mid, r);
    }
    T find_sum(int x, int y, T val){
        return find_sum(x, y, val, 1, 0, n);
    }
};

long long brute(int l, int r, int k){
    vector<int> cur;
    for (int i = l; i <= r; i++) cur.push_back(a[i]);
    sort(cur.begin(), cur.end());
    long long ans = 0;
    for (int i = 0; i < k; i++) ans += cur[i];
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    freopen("input.txt", "r", stdin);

    int n;
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    b = a;
    sort(b.begin(), b.end());
    segtree<long long> T(n);
    T.build(1, 0, T.n); // [l,r)

    int q;
    cin >> q;
    while (q--){
        int l, r, k;
        cin >> l >> r >> k;

        int L = 0, R = n - 1, x, cnt;
        while (L <= R){
            int mid = (L + R) >> 1;
            int cur = T.find_cnt(l, r + 1, b[mid]);
            if (cur >= k){
                cnt = cur;
                x = b[mid];
                R = mid - 1;
            }
            else{
                L = mid + 1;
            }
        }

        long long ans = T.find_sum(l, r + 1, x);
        ans -= 1ll * x * (cnt - k);
        cout << ans << endl;
    }
    return 0;
}