#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
const int maxn = 500005;
const int inf = 1e17;
using namespace std;
//W segtree
struct segtree {
int t[2 * maxn], n;
void build() {
for (int i = n - 1; i > 0; --i)
t[i] = t[i << 1] + t[i << 1 | 1];
}
void update(int p, int value) {
for (t[p += n] = value; p > 1; p >>= 1)
t[p >> 1] = t[p] + t[p ^ 1];
}
int query(int l, int r) {
int res = 0;
for (l += n, r += (n + 1); l < r; l >>= 1, r >>= 1) {
if (l & 1) res += t[l++];
if (r & 1) res += t[--r];
}
return res;
}
void init(int N, vector<int> a) {
for (int i = 0; i < N; ++i)
t[i + N] = a[i];
n = N, build();
}
};
/////////////////////////////////////////////////////////////////
vector<int> a, res, idx;
vector<pair<int, int>> arr;
vector<pair<int, pair<int, int>>> qs;
segtree s1, s2;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
a.resize(n), idx.resize(n), arr.resize(n);
for (auto& x : a) cin >> x;
for (int i = 0; i < n; ++i)
arr[i] = { a[i], i };
sort(arr.begin(), arr.end());
for (int i = 0; i < n; ++i)
idx[arr[i].second] = i;
s1.init(n, vector<int>(n, 0));
s2.init(n, vector<int>(n, 0));
int q, k = 0; cin >> q;
while (q--) {
int t; cin >> t;
if (t == 1) ++k;
else {
int l, r; cin >> l >> r; l -= 2, --r;
if (l >= 0) qs.push_back({ l + k + 1, {l + 1, -(int)res.size() - 1} });
qs.push_back({ r + k + 1, {r + 1, res.size() + 1 } });
res.push_back(0);
}
}
sort(qs.begin(), qs.end());
int j = 0;
for (int i = 0; i < qs.size(); ++i) {
while ((j < n) && (j < qs[i].first))
s1.update(idx[j], a[j]), s2.update(idx[j], 1), ++j;
int s = 0, e = n - 1, ksm = n - 1;
while (s <= e) {
int m = (s + e) / 2;
if (s2.query(0, m) >= qs[i].second.first)
ksm = m, e = m - 1;
else s = m + 1;
}
int ans = s1.query(0, ksm);
int l = qs[i].second.second;
res[abs(l) - 1] += (l / abs(l)) * ans;
}
for (auto x : res) cout << x << endl;
}
