#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll arr[100005];
struct info{
ll l,r,exsum,ppl;
};
void norm_pref(vector<info>& a){
if(a.size()<=1)return;
if(a[a.size()-1].r!=a[a.size()-2].r)return;
ll cur=a[a.size()-1].ppl;
a.pop_back();
a[a.size()-1].ppl+=cur;
}
void norm_suff(vector<info>& a){
if(a.size()<=1)return;
if(a[a.size()-1].l!=a[a.size()-2].l)return;
ll cur=a[a.size()-1].ppl;
a.pop_back();
a[a.size()-1].ppl+=cur;
}
void merge_pref(vector<info>& a, vector<info> b){
vector<info>k;
ll ptr=0,ptr2=0;
while(ptr<a.size()&&ptr2<b.size()){
if(a[ptr].r<b[ptr2].r){k.push_back(a[ptr]); ptr++;}
else{k.push_back(b[ptr2]); ptr2++;}
norm_pref(k);
}
if(ptr<a.size()){
for(int i=ptr;i<a.size();i++){
k.push_back(a[i]); norm_pref(k);
}
}
else{
for(int i=ptr2;i<b.size();i++){
k.push_back(b[i]); norm_pref(k);
}
}
a.swap(k);
}
void merge_suff(vector<info>& a, vector<info> b){
vector<info>k;
ll ptr=0,ptr2=0;
while(ptr<a.size()&&ptr2<b.size()){
if(a[ptr].l>b[ptr2].l){k.push_back(a[ptr]); ptr++;}
else{k.push_back(b[ptr2]); ptr2++;}
norm_suff(k);
}
if(ptr<a.size()){
for(int i=ptr;i<a.size();i++){
k.push_back(a[i]); norm_suff(k);
}
}
else{
for(int i=ptr2;i<b.size();i++){
k.push_back(b[i]); norm_suff(k);
}
}
a.swap(k);
}
void normalize(vector<info>& a){
for(int i=a.size()-1;i>=1;i--){
a[i].exsum-=a[i-1].exsum;
}
}
struct node{
vector<info>pref; vector<info>suff;
void set(ll pos, ll val){
pref.clear(); suff.clear();
pref.push_back({pos,pos,val,1}); suff.push_back({pos,pos,val,1});
}
node operator+(const node& nd)const{
// 2-ptr
// merge my suff and nd's pref
vector<info>npref,nsuff,nnpref,nnsuff,rpref,rsuff;
rpref=pref; rsuff=nd.suff;
for(int i=1;i<rpref.size();i++){
rpref[i].exsum+=rpref[i-1].exsum;
}
for(int i=1;i<rsuff.size();i++){
rsuff[i].exsum+=rsuff[i-1].exsum;
}
rpref.pop_back(); rsuff.pop_back();
ll ptrme=0,ptrhim=-1,cursum=suff[0].exsum;
for(int i=0;i<suff.size();i++){
while(ptrme<i){
ptrme++; cursum+=suff[ptrme].exsum;
}
while(1){
if(ptrme+1<suff.size()){
if(cursum>=arr[suff[ptrme].l-1]){
ptrme++; cursum+=suff[ptrme].exsum;
continue;
}
}
if(ptrhim+1<nd.pref.size()){
if(ptrhim==-1){
if(cursum>=arr[nd.pref[ptrhim+1].l]){
ptrhim++; cursum+=nd.pref[ptrhim].exsum;
continue;
}
}
else{
if(cursum>=arr[nd.pref[ptrhim].r+1]){
ptrhim++; cursum+=nd.pref[ptrhim].exsum;
continue;
}
}
}
break;
}
if(ptrme==(int)suff.size()-1){
if(ptrhim==-1){
npref.push_back({suff[ptrme].l,suff[ptrme].r,cursum,suff[i].ppl});
}
else{
npref.push_back({suff[suff.size()-1].l,nd.pref[ptrhim].r,cursum,suff[i].ppl});
}
}
if(ptrhim==(int)nd.pref.size()-1){
nsuff.push_back({suff[ptrme].l,nd.pref[ptrhim].r,cursum,suff[i].ppl});
}
}
ptrme=-1,ptrhim=0,cursum=nd.pref[0].exsum;
for(int i=0;i<nd.pref.size();i++){
while(ptrhim<i){
ptrhim++; cursum+=nd.pref[ptrhim].exsum;
}
while(1){
if(ptrhim+1<nd.pref.size()){
if(cursum>=arr[nd.pref[ptrhim].r+1]){
ptrhim++; cursum+=nd.pref[ptrhim].exsum;
continue;
}
}
if(ptrme+1<suff.size()){
if(ptrme==-1){
if(cursum>=arr[suff[ptrme+1].r]){
ptrme++; cursum+=suff[ptrme].exsum;
continue;
}
}
else{
if(cursum>=arr[suff[ptrme].l-1]){
ptrme++; cursum+=suff[ptrme].exsum;
continue;
}
}
}
break;
}
if(ptrhim==(int)nd.pref.size()-1){
if(ptrme==-1){
nnsuff.push_back({nd.pref[ptrhim].l,nd.pref[ptrhim].r,cursum,nd.pref[i].ppl});
}
else{
nnsuff.push_back({suff[ptrme].l,nd.pref[ptrhim].r,cursum,nd.pref[i].ppl});
}
}
if(ptrme==(int)suff.size()-1){
nnpref.push_back({suff[ptrme].l,nd.pref[ptrhim].r,cursum,nd.pref[i].ppl});
}
}
merge_pref(rpref,npref); merge_pref(rpref,nnpref);
merge_suff(rsuff,nsuff); merge_suff(rsuff,nnsuff);
normalize(rsuff); normalize(rpref);
return {rpref,rsuff};
}
};
struct SEG{
vector<node>seg;
vector<ll>a;
void init(ll n){
seg.resize(4*n+5); a.resize(n+5);
}
void build(ll l, ll r, ll id){
if(l==r){
seg[id].set(l,a[l]); return;
}
ll mid=(l+r)>>1;
build(l,mid,id*2); build(mid+1,r,id*2+1);
seg[id]=seg[id*2]+seg[id*2+1];
}
void upd(ll ul, ll l, ll r, ll val, ll id){
if(l==r){
seg[id].set(l,val); return;
}
ll mid=(l+r)>>1;
if(ul<=mid)upd(ul,l,mid,val,id*2);
else upd(ul,mid+1,r,val,id*2+1);
seg[id]=seg[id*2]+seg[id*2+1];
}
node qry(ll ql, ll qr, ll l, ll r, ll id){
if(l>=ql&&r<=qr){
return seg[id];
}
ll mid=(l+r)>>1;
node ans;
if(l>qr||mid<ql)return qry(ql,qr,mid+1,r,id*2+1);
else ans=qry(ql,qr,l,mid,id*2);
if(mid+1>qr||r<ql)return ans;
else ans=ans+qry(ql,qr,mid+1,r,id*2+1);
return ans;
}
}st;
ll val(node nd){
ll sz=nd.pref.size();
return nd.pref[sz-1].ppl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n;
cin>>n;
for(int i=1;i<=n;i++)cin>>arr[i];
st.init(n);
for(int i=1;i<=n;i++)st.a[i]=arr[i];
st.build(1,n,1);
ll q; cin>>q;
while(q--){
ll tp;
cin>>tp;
if(tp==1){
ll x,y;
cin>>x>>y; arr[x]=y;
st.upd(x,1,n,y,1);
}
else{
ll l,r;
cin>>l>>r;
cout<<val(st.qry(l,r,1,n,1))<<'\n';
}
}
}
