#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"; } } }