#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct T {
ll cnt, sum;
T operator+(T other) { return T{cnt + other.cnt, sum + other.sum}; };
};
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
ll N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; ++i) cin >> A[i];
// (query index, n, sgn)
vector<vector<tuple<ll, ll, ll>>> query(N + 1);
ll Q;
cin >> Q;
ll op = 0;
vector<ll> ANS;
for (int q = 0; q < Q; ++q) {
ll t;
cin >> t;
if (t == 1) ++op;
if (t == 2) {
ll L, R;
cin >> L >> R;
--L;
ll idx = ANS.size();
ANS.push_back(0);
query[min(op + L, N)].push_back(make_tuple(idx, L, -1));
query[min(op + R, N)].push_back(make_tuple(idx, R, +1));
}
}
// index compress
vector<int> I(N);
for (int i = 0; i < N; ++i) I[i] = i;
sort(I.begin(), I.end(), [&](int i, int j) -> bool { return A[i] < A[j]; });
vector<int> rank(N);
for (int i = 0; i < N; ++i) rank[I[i]] = i;
vector<T> bit(N + 1);
for (int n = 0; n <= N; ++n) {
for (auto &[idx, m, sgn]: query[n]) {
ll cnt = 0, sm = 0;
ll p = 0;
// binary search on Fenciwk Tree
for (int i = 20; i >= 0; --i) {
if (p + (1 << i) > N) continue;
auto [c, s] = bit[p + (1 << i)];
if (cnt + c > m) continue;
cnt += c, sm += s, p += 1 << i;
}
ANS[idx] += sm * sgn;
}
if (n == N) break;
int i = rank[n];
// add to Fenwick Tree
++i;
T t = {1, A[n]};
while (i <= N) {
bit[i] = bit[i] + t;
i += i & (-i);
}
}
for (ll x: ANS) cout << x << "\n";
}
