#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct fenwick {
int sz;
const int LOG = 20;
vector<int> ct;
vector<ll> fw;
fenwick(int n) {
sz = n+1;
ct.resize(sz);
fw.resize(sz);
}
void add(int i, int fw_val) {
int ct_val = (fw_val > 0 ? 1 : -1);
for(i++; i<sz; i+= i & -i) {
fw[i] += fw_val;
ct[i] += ct_val;
}
}
pair<ll, int> sum(int i) {
ll fw_sum = 0;
int ct_sum = 0;
for(; i>0; i -= i & -i) fw_sum += fw[i], ct_sum += ct[i];
return {fw_sum, ct_sum};
}
ll query(int x) {
int id = 0;
ll sum = 0;
for(int i=(1 << LOG); i >= 0 ; i /= 2) {
if(id + i < sz and ct[id + i] <= x) {
sum += fw[id + i];
x -= ct[id + i];
id += i;
}
if(i == 0) break;
}
return sum;
}
};
int main() {
int n; cin >> n;
vector<int> v(n);
for(int &x: v) cin >> x;
vector<int> perm(n);
iota(perm.begin(), perm.end(), 0);
sort(perm.begin(), perm.end(), [&](int a, int b) {
if(v[a] == v[b]) return a < b;
return v[a] < v[b];
});
vector<int> inv_perm(n);
for(int i=0; i<n; i++) {
inv_perm[perm[i]] = i;
}
vector<vector<int>> bigger(n);
fenwick fw(n);
for(int i=0; i<n; i++) {
bigger[i - fw.sum(inv_perm[i]).second].push_back(i);
fw.add(inv_perm[i], v[i]);
}
// for(auto v: bigger) {
// for(int x: v) cerr << x << " ";
// cerr << endl;
// }
fenwick small(n);
for(int i=0; i<n; i++) {
small.add(i, v[i]);
}
fenwick big(n);
int steps = 0;
auto get_prefix = [&](int i) -> ll {
auto [sum_small, ct_small] = small.sum(min(n, i + steps));
int ct_big = i - ct_small;
ll sum_big = big.query(ct_big);
// cerr << sum_small << " " << sum_big << endl;
return sum_small + sum_big;
};
int q; cin >> q;
while(q--) {
int t; cin >> t;
if(t == 1) {
if(steps >= bigger.size()) continue;
for(int i: bigger[steps]) {
small.add(i, -v[i]);
big.add(inv_perm[i], v[i]);
}
steps++;
}
if(t == 2) {
int l, r; cin >> l >> r; l--;
cout << get_prefix(r) - get_prefix(l) << "\n";
}
}
}
