#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#pragma GCC optimize("Ofast,unroll-loops")
const int N=5e5+50,inf=1e9,lg=20;
int n,q,a[N];
struct Wavelet{
int root,nc,lc[N*lg],rc[N*lg];
vector<int>a[N*lg];
vector<ll>prefL[N*lg],pref[N*lg];
void Build(int &c,int ss,int se,vector<int>A,vector<int>A1){
if(A.empty()||ss>se)return;
c=++nc;
//printf("%i: %i %i\n",c,ss,se);
a[c].resize(A.size()+1);
prefL[c].resize(A.size()+1);
pref[c].resize(A.size()+1);
int mid=ss+se>>1;
vector<int>B,B1,C,C1;
for(int i=0;i<A.size();i++){
a[c][i+1]=a[c][i];
prefL[c][i+1]=prefL[c][i];
pref[c][i+1]=pref[c][i]+A1[i];
if(A[i]<=mid){
B.pb(A[i]);
B1.pb(A1[i]);
a[c][i+1]++;
prefL[c][i+1]+=A1[i];
}
else{
C.pb(A[i]);
C1.pb(A1[i]);
}
}
if(ss==se)return;
Build(lc[c],ss,mid,B,B1);
Build(rc[c],mid+1,se,C,C1);
}
ll Get(int c,int ss,int se,int l,int r,int k){
if(!c||l>r||k==0)return 0;
if(ss==se)return pref[c][l+k]-pref[c][l];
int mid=ss+se>>1;
if(a[c][r+1]-a[c][l]>=k)return Get(lc[c],ss,mid,a[c][l],a[c][r+1]-1,k);
return Get(rc[c],mid+1,se,l-a[c][l],r-a[c][r+1],k-(a[c][r+1]-a[c][l]))+prefL[c][r+1]-prefL[c][l];
}
}ST;
int M,K;
ll Calc(int l){
int k=min(K,n-l);
return ST.Get(ST.root,0,M,0,l+k-1,l);
}
int main(){
scanf("%i",&n);
for(int i=1;i<=n;i++)scanf("%i",&a[i]);
vector<int>A,vals;
for(int i=1;i<=n;i++)A.pb(a[i]),vals.pb(a[i]);
sort(vals.begin(),vals.end());
vals.resize(unique(vals.begin(),vals.end())-vals.begin());
vector<int>A1;
for(auto i:A)A1.pb(lower_bound(vals.begin(),vals.end(),i)-vals.begin());
M=vals.size()-1;
ST.Build(ST.root,0,M,A1,A);
scanf("%i",&q);
while(q--){
int type;scanf("%i",&type);
if(type==1)K++;
else{
int l,r;scanf("%i%i",&l,&r);
ll res=Calc(r)-Calc(l-1);
printf("%lld\n",res);
}
}
return 0;
}
