#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define task "bubble"
const int N = 5e5+5;
ll a[N],ans[N];
pair<ll,ll> arr[N];
ll pos[N];
int n,q;
vector<pair<int,int>> query[N];
struct segtree{
ll st[4*N],alive[4*N];
void update(int id,int l,int r,int p){
if(l==r){
alive[id]=1;
st[id]=a[l];
return;
}
int mid=(l+r)>>1;
if(mid<p) update(id<<1|1,mid+1,r,p);
else update(id<<1,l,mid,p);
st[id]=(st[id<<1]+st[id<<1|1]);
alive[id]=(alive[id<<1]+alive[id<<1|1]);
}
ll get(int id,int l,int r,int k){
if(k == 0) return 0;
if(alive[id] == k) return st[id];
int mid=(l+r)>>1;
if(alive[id<<1] >= k) return get(id<<1,l,mid,k);
else return st[id<<1]+get(id<<1|1,mid+1,r,k-alive[id<<1]);
}
}st;
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
arr[i]={a[i],i};
}
sort(arr+1,arr+1+n);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) pos[arr[i].se]=i;
cin>>q;
int K=0;
for(int i=1;i<=q;i++){
int T;
cin>>T;
if(T == 1) K++;
else{
int l,r;
cin>>l>>r;
query[min(n,r+K)].push_back({r,i});
query[min(n,l-1+K)].push_back({l-1,-i});
}
}
for(int i=1;i<=n;i++){
int p=pos[i];
st.update(1,1,n,p);
for(auto [k,idx]:query[i]){
ll t=st.get(1,1,n,k);
if(idx>0) ans[idx] += t;
else ans[-idx] -= t;
}
}
for(int i=1;i<=q;i++){
if(ans[i]>0) cout<<ans[i]<<'\n';
}
}
