#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
const int lim = 5e5 + 5;
int n, q, cnt_query = 0, a[lim];
ll ans[lim];
vector<pair<int, int>>comp, query[lim];
struct FenwickTree{
ll bit[lim];
FenwickTree(){
memset(bit, 0, sizeof(bit));
}
void update(int p, int x){
for(; p <= n; p += p & -p){
bit[p] += x;
}
}
};
FenwickTree s, c;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n;
for(int i = 1; i <= n; comp.push_back(make_pair(a[i], i)), i++){
cin >> a[i];
}
cin >> q;
for(int i = 0, k = 0; i < q; i++){
int t, l, r;
cin >> t;
if(t == 1){
k++;
}
else{
cin >> l >> r;
query[min(n, r + k)].push_back(make_pair(++cnt_query, r));
if(l > 1){
query[min(n, l - 1 + k)].push_back(make_pair(-cnt_query, l - 1));
}
}
}
memset(ans, 0, sizeof(ans));
sort(comp.begin(), comp.end());
for(int i = 1; i <= n; i++){
int p = lower_bound(comp.begin(), comp.end(), make_pair(a[i], i)) - comp.begin() + 1;
c.update(p, 1);
s.update(p, a[i]);
for(auto& [id, need] : query[i]){
for(int bit = 18, pos = 0; bit > -1; bit--){
int npos = pos + (1 << bit);
if(npos <= n && need >= c.bit[npos]){
need -= c.bit[pos = npos];
if(id < 0){
ans[-id] -= s.bit[pos];
}
else{
ans[id] += s.bit[pos];
}
}
}
}
}
for(int i = 1; i <= cnt_query; i++){
cout << ans[i] << "\n";
}
}
