#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define me(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
const int MAXN=5e5+5;
ll A[MAXN],sum[MAXN*4],tam[MAXN*4];
vector<ii>ini[MAXN],fin[MAXN];
int n;
void upd(int p,int x,int v=1,int s=0,int e=n-1){
if(s==e){
sum[v]+=x;
tam[v]++;
return;
}
int m=(s+e)/2;
if(p<=m)upd(p,x,v*2,s,m);
else upd(p,x,v*2+1,m+1,e);
sum[v]=sum[v*2]+sum[v*2+1];
tam[v]=tam[v*2]+tam[v*2+1];
}
ll kth_sum(ll k,int v=1,int s=0,int e=n-1){
if(tam[v]==0)return 0;
if(s==e){
ll x=sum[v]/tam[v];
return x*k*1ll;
}
int m=(s+e)/2;
if(k<=tam[v*2])return kth_sum(k,v*2,s,m);
else return sum[v*2]+kth_sum(k-tam[v*2],v*2+1,m+1,e);
}
int main(){FIN;
cin>>n;
vi compress;
fore(i,0,n){
cin>>A[i];
compress.pb(A[i]);
}
sort(ALL(compress));
compress.erase(unique(ALL(compress)),compress.end());
fore(i,0,n){
A[i]=lower_bound(ALL(compress),A[i])-compress.begin();
}
int Q;cin>>Q;
int lim=0,C=0;
while(Q--){
int t;cin>>t;
if(t==1)lim++;
else{
int l,r;cin>>l>>r;
l--;r--;
ini[min(n-1,l+lim-1)].pb({l,C});
fin[min(n-1,r+lim)].pb({r+1,C});
C++;
}
}
vi ans(C,0);
//~ cout<<"HOLA"<<endl;
fore(i,0,n){
upd((int)A[i],(int)compress[A[i]]);
for(auto[j,idx]:ini[i]){
ans[idx]-=kth_sum(j);
//~ cout<<"RESTA :"<<idx<<" "<<ans[idx]<<endl;
}
for(auto[j,idx]:fin[i]){
ans[idx]+=kth_sum(j);
//~ cout<<"SUMA :"<<idx<<" "<<ans[idx]<<endl;
}
}
//~ cout<<"HOLAA"<<endl;
fore(i,0,C)cout<<ans[i]<<endl;
}
