#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = (1LL<<19); const ll E = 19;
ll v2(ll x) {
if (x==0) {
return 100;
}
return __builtin_ctz(x);
}
struct st { //segtree
vector<ll> st0 = vector<ll>(2*Nm,0);
void upd(ll x, ll v) {
ll p = x+Nm;
do {
st0[p]+=v;
p=p/2;
} while (p>0);
}
ll qry(ll a, ll b) {
if (a>b) {
return 0;
}
ll va = v2(a); ll vb = v2(b+1);
if (va<vb) {
return (st0[(1LL<<(E-va))+(a>>va)]+qry(a+(1LL<<va),b));
} else {
return (st0[(1LL<<(E-vb))+(b>>vb)]+qry(a,b-(1LL<<vb)));
}
}
};
st stb; //for B[N]
st stav; //segtree of active values (b-index to value)
st stan; //segtree of active indices (normal)
st stab; //segtree of active indices (b-index)
st stiv; //segtree of inactive values
void act(ll x, ll b, ll a) {
//cout << "act: "<<x<<","<<b<<","<<a<<"\n";
stiv.upd(x,-a);
stav.upd(b,a);
stan.upd(x,1);
stab.upd(b,1);
}
ll clc(ll x) {
if (x==-1) {
return 0;
}
//first get b-index of the x+1th smallest term
ll bmin = 0; ll bmax = Nm-1;
while (bmin != bmax) {
ll bcen = (bmin+bmax)/2;
ll nact = stab.qry(0,bcen); //sum of all in [0,bcen]
if (nact==(x+1)) {
bmin = bcen; bmax = bcen;
} else if (nact>(x+1)) {
bmax = bcen-1;
} else {
bmin = bcen+1;
}
}
//cout << "bmin="<<bmin<<"\n";
return (stav.qry(0,bmin));
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
ll N; cin >> N;
ll A[N];
ll B[N]; //compressed A
vector<pii> vb;
for (ll i=0;i<N;i++) {
cin >> A[i];
vb.push_back({A[i],i});
stiv.upd(i,A[i]);
}
sort(vb.begin(),vb.end());
ll srtps[N+1];
srtps[0]=0;
for (ll j=0;j<N;j++) {
B[vb[j].second]=j;
srtps[j+1]=srtps[j]+vb[j].first;
}
vector<ll> incl[N]; //indices (vector) to add at a given time T
ll T = 0; //time
for (ll x=0;x<N;x++) {
incl[stb.qry(B[x]+1,Nm-1)].push_back(x);
stb.upd(B[x],1);
}
for (ll v0: incl[0]) {
act(v0, B[v0], A[v0]);
}
ll Q; cin >> Q;
for (ll q=0;q<Q;q++) {
ll tj; cin >> tj;
if (tj==1) {
if (T<(N-1)) {
stan.upd(T,-1);
T++;
for (ll v0: incl[T]) {
act(v0,B[v0],A[v0]);
}
}
} else {
ll l,r; cin >> l >> r; l--; r--;
ll ans = 0;
if (r>=(N-T)) {
ll l1 = max(l,N-T);
// ans += ((r*(r+1))/2)-((l1*(l1+1))/2);
ans += srtps[r+1]-srtps[l1];
//cout << "anst1="<<ans<<"\n";
}
if (l<=(N-1-T)) {
ll r1 = min(r,N-T-1)+T;
ll l1 = l+T;
ans += stiv.qry(l1,r1);
//cout << "anst2="<<ans<<"\n";
ll x = stan.qry(0,l1-1)-1;
ll y = stan.qry(0,r1)-1; //get all active values with b-indices in (x,y]
//cout << "x,y="<<x<<","<<y<<"\n";
ans -= clc(x); //calculate
ans += clc(y);
//cout << "anst3="<<ans<<"\n";
}
cout << ans << "\n";
}
}
}
