#include<bits/stdc++.h>
using namespace std;
#define int int64_t
int f[600000] , f2[600000];
void add(int p , int v){
while(p < 600000){
f[p]+=v;
p +=(-p)&p;
}
}
int get(int p){
int ans = 0;
while(p>0){
ans += f[p];
p -= (-p)&p;
}
return ans;
}
void add2(int p , int v){
while(p < 600000){
f2[p]+=v;
p +=(-p)&p;
}
}
int get2(int p){
int ans = 0;
while(p>0){
ans += f2[p];
p -= (-p)&p;
}
return ans;
}
int32_t main(){
int n; cin >> n;
vector<array<int , 2>> a , c(n);
vector<int> p;p.push_back(0);
for(int i = 0; i < n; i++){
int x; cin >> x;
a.push_back({x , i});
p.push_back(p.back()+x);
}
sort(a.begin() , a.end());
for(int i = 0; i < n; i++){
c[a[i][1]] = {a[i][0] , i};
}
int q;cin >> q;
int u = 0;
vector<array<int , 4>> o;
vector<int> ans;
while(q--){
int b; cin >> b;
if(b==1){
u++;
continue;
}
int l , r; cin >> l >> r;
o.push_back({min(l-1+u , n)-1 , min(l-1+u , n)-(l-1) , int(ans.size()) , 1});
o.push_back({min(r+u , n)-1 , min(r+u , n)-(r) , int(ans.size()) , -1});
int h = 0;
h += p[r]-p[l-1];
h -= p[min(l+u-1 , n)]-p[l-1];
h += p[min(r+u , n)]-p[r];
ans.push_back(h);
}
sort(o.begin() , o.end());
int j = -1;
for(int i = 0; i < o.size(); i++){
while(j < o[i][0]){
j++;
add(n-c[j][1] , c[j][0]);
add2(n-c[j][1] , 1);
}
int l = 0 , r = 600000;
while(l+1 != r){
int m = (l+r)/2;
if(get2(m) > o[i][1])r=m; else l=m;
}
ans[o[i][2]] += o[i][3]*get(l);
}
for(int x : ans) cout << x << "\n";
}
