#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int lg(ll x) {
assert(x > 0);
return __builtin_clzll(1) - __builtin_clzll(x);
}
struct BIT {
vector<ll> t;
BIT(int n) : t(n + 1) {}
void add(int k, ll x) {
while(k < t.size()) t[k] += x, k += k&-k;
}
ll sum(int k) {
ll sm = 0;
while(k > 0) sm += t[k], k -= k&-k;
return sm;
}
int lb(ll sm) {
int k = 0;
for(int j = 1 << lg(t.size() - 1); j > 0; j /= 2) {
if(t[k + j] < sm) k += j, sm -= t[k];
}
return k;
}
};
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int N; cin >> N;
vector<int> a(N);
for(int i = 0; i < N; i++) cin >> a[i];
vector<int> sa = a;
sort(sa.begin(), sa.end());
sa.resize(unique(sa.begin(), sa.end()) - sa.begin());
map<int, int> id;
for(int i = 0; i < sa.size(); i++) id[sa[i]] = i;
BIT bit(sa.size());
BIT bit2(sa.size());
int Q; cin >> Q;
int k = 0;
vector<pair<int, int>> queries;
while(Q--) {
int T; cin >> T;
if(T == 1) {
k++;
} else {
int l, r; cin >> l >> r;
queries.push_back({l - 1, k});
queries.push_back({r, k});
}
}
int q = queries.size();
vector<int> o(q);
iota(o.begin(), o.end(), 0);
sort(o.begin(), o.end(), [&] (int x, int y) {
auto& [r1, k1] = queries[x];
auto& [r2, k2] = queries[y];
return r1 + k1 < r2 + k2;
});
vector<ll> ans(q);
int j = 0;
for(int i : o) {
auto& [r, k] = queries[i];
while(j < N && j < r + k) {
bit.add(id[a[j]] + 1, 1);
bit2.add(id[a[j]] + 1, a[j]);
j++;
}
int sp = bit.lb(r);
ans[i] = bit2.sum(sp + 1) - (bit.sum(sp + 1) - r) * sa[sp];
}
for(int i = 0; i < q; i += 2) {
cout << ans[i + 1] - ans[i] << '\n';
}
}
