#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e17;
typedef pair<int,int> pii;
ll n,v[100005],q,s[100005],mars[100005];
int solve(int l,int r)
{
s[l-1]=0;
mars[l-1]=0;
for(int i=l;i<=r;i++)
{
s[i]=s[i-1]+v[i];
mars[i]=0;
}
stack<int> coada;
for(int i=l;i<=r;i++)
{
while(!coada.empty()&&v[coada.top()]<v[i])
coada.pop();
int st=l-1;
if(!coada.empty())
st=coada.top();
if(s[i-1]-s[st]<v[i])
{
mars[st+1]++;
mars[i]--;
}
coada.push(i);
}
while(!coada.empty())
coada.pop();
for(int i=r;i>=l;i--)
{
while(!coada.empty()&&v[coada.top()]<v[i])
coada.pop();
int dr=r+1;
if(!coada.empty())
dr=coada.top();
if(s[dr-1]-s[i]<v[i])
{
mars[i+1]++;
mars[dr]--;
}
coada.push(i);
}
int ans=0;
for(int i=l;i<=r;i++)
{
mars[i]+=mars[i-1];
if(mars[i]==0)
ans++;
}
return ans;
}
ll aib[100005];
ll lsb(ll x)
{
return x&(-x);
}
void aibupd(ll poz,ll val)
{
for(int i=poz;i<=n;i+=lsb(i))
aib[i]+=val;
}
ll suma(ll poz)
{
ll rez=0;
for(int i=poz;i>=1;i-=lsb(i))
rez+=aib[i];
return rez;
}
struct date
{
ll minim,cnt;
} arb[4*100005];
ll toprop[4*100005];
struct prostie
{
ll maxim,poz;
} arbdir[2][4*100005]; /// 0 -> st, 1 -> dr
ll topropdir[2][4*100005];
date combine(date a, date b)
{
if(a.minim<b.minim)
return a;
if(a.minim>b.minim)
return b;
a.cnt+=b.cnt;
return a;
}
void prop(ll nod)
{
ll val=toprop[nod];
arb[nod*2].minim+=val;
arb[nod*2+1].minim+=val;
toprop[nod*2]+=val;
toprop[nod*2+1]+=val;
}
void update(ll nod,ll st,ll dr,ll a,ll b,ll val)
{
if(st!=dr)
prop(nod);
toprop[nod]=0;
if(st>=a&&dr<=b)
{
arb[nod].minim+=val;
toprop[nod]+=val;
return;
}
ll mij=(st+dr)/2;
if(a<=mij)
update(nod*2,st,mij,a,b,val);
if(b>mij)
update(nod*2+1,mij+1,dr,a,b,val);
arb[nod]=combine(arb[nod*2],arb[nod*2+1]);
}
date query(ll nod,ll st,ll dr,ll a,ll b)
{
if(st!=dr)
prop(nod);
toprop[nod]=0;
if(st>=a&&dr<=b)
return arb[nod];
date rez={2LL*INF,0};
ll mij=(st+dr)/2;
if(a<=mij)
rez=combine(rez,query(nod*2,st,mij,a,b));
if(b>mij)
rez=combine(rez,query(nod*2+1,mij+1,dr,a,b));
return rez;
}
prostie combinedir(prostie a, prostie b)
{
if(a.maxim>=b.maxim)
return a;
return b;
}
void propdir(ll ind,ll nod)
{
ll val=topropdir[ind][nod];
arbdir[ind][nod*2].maxim+=val;
arbdir[ind][nod*2+1].maxim+=val;
topropdir[ind][nod*2]+=val;
topropdir[ind][nod*2+1]+=val;
}
void updatedir(ll ind,ll nod,ll st,ll dr,ll a,ll b,ll val)
{
if(st!=dr)
propdir(ind,nod);
topropdir[ind][nod]=0;
if(st>=a&&dr<=b)
{
arbdir[ind][nod].maxim+=val;
topropdir[ind][nod]+=val;
return;
}
ll mij=(st+dr)/2;
if(a<=mij)
updatedir(ind,nod*2,st,mij,a,b,val);
if(b>mij)
updatedir(ind,nod*2+1,mij+1,dr,a,b,val);
arbdir[ind][nod]=combinedir(arbdir[ind][nod*2],arbdir[ind][nod*2+1]);
}
prostie querydir(ll ind,ll nod,ll st,ll dr,ll a,ll b)
{
if(st!=dr)
propdir(ind,nod);
topropdir[ind][nod]=0;
if(st>=a&&dr<=b)
return arbdir[ind][nod];
prostie rez={-2LL*INF,0};
ll mij=(st+dr)/2;
if(a<=mij)
rez=combinedir(rez,querydir(ind,nod*2,st,mij,a,b));
if(b>mij)
rez=combinedir(rez,querydir(ind,nod*2+1,mij+1,dr,a,b));
return rez;
}
void build(int nod,int st,int dr)
{
arb[nod].cnt=(dr-st+1);
if(st==dr)
return;
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
}
void builddir(int nod,int st,int dr)
{
arbdir[0][nod]=arbdir[1][nod]={0,st};
if(st==dr)
return;
int mij=(st+dr)/2;
builddir(nod*2,st,mij);
builddir(nod*2+1,mij+1,dr);
}
set<pii> setik;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>v[i];
cin>>q;
v[0]=INF;
v[n+1]=INF;
build(1,1,n);
builddir(1,1,n);
for(int i=1;i<=n;i++)
aibupd(i,v[i]);
stack<int> coada;
for(int i=1;i<=n;i++)
{
while(!coada.empty()&&v[coada.top()]<v[i])
coada.pop();
int st=0;
if(!coada.empty())
st=coada.top();
if(suma(i-1)-suma(st)<v[i])
{
/*mars[st+1]++;
mars[i]--;*/
if(st+1<=i-1)
setik.insert({st+1,i-1});
}
coada.push(i);
}
while(!coada.empty())
coada.pop();
for(int i=n;i>=1;i--)
{
while(!coada.empty()&&v[coada.top()]<v[i])
coada.pop();
int dr=n+1;
if(!coada.empty())
dr=coada.top();
if(suma(dr-1)-suma(i)<v[i])
{
/*mars[i+1]++;
mars[dr]--;*/
if(i+1<=dr-1)
setik.insert({i+1,dr-1});
}
coada.push(i);
}
while(!coada.empty())
coada.pop();
for(int i=1;i<=n;i++)
{
updatedir(0,1,1,n,i,i,v[i]);
updatedir(1,1,1,n,i,i,v[i]);
if(i+1<=n)
updatedir(0,1,1,n,i+1,n,-v[i]);
if(i-1>=1)
updatedir(1,1,1,n,1,i-1,-v[i]);
}
for(auto p:setik)
update(1,1,n,p.first,p.second,+1);
while(q--)
{
ll tip;
cin>>tip;
if(tip==1)
{
ll i,val;
cin>>i>>val;
updatedir(0,1,1,n,i,i,-v[i]);
updatedir(1,1,1,n,i,i,-v[i]);
if(i+1<=n)
updatedir(0,1,1,n,i+1,n,v[i]);
if(i-1>=1)
updatedir(1,1,1,n,1,i-1,v[i]);
aibupd(i,-v[i]);
v[i]=val;
updatedir(0,1,1,n,i,i,v[i]);
updatedir(1,1,1,n,i,i,v[i]);
if(i+1<=n)
updatedir(0,1,1,n,i+1,n,-v[i]);
if(i-1>=1)
updatedir(1,1,1,n,1,i-1,-v[i]);
aibupd(i,v[i]);
vector<int> lft,rgt;
if(i>1)
{
ll S=suma(n)-suma(i-1);
while(true)
{
prostie a=querydir(1,1,1,n,1,i-1);
a.maxim+=S;
if(a.maxim<0)
break;
lft.push_back(a.poz);
updatedir(1,1,1,n,a.poz,a.poz,-INF);
}
for(ll p:lft)
updatedir(1,1,1,n,p,p,+INF);
}
if(i+1<=n)
{
ll S=suma(i);
while(true)
{
prostie a=querydir(0,1,1,n,i+1,n);
a.maxim+=S;
if(a.maxim<0)
break;
rgt.push_back(a.poz);
updatedir(0,1,1,n,a.poz,a.poz,-INF);
}
for(ll p:rgt)
updatedir(0,1,1,n,p,p,+INF);
}
lft.push_back(i);
rgt.push_back(i);
lft.push_back(0);
rgt.push_back(n+1);
for(ll l:lft)
for(ll r:rgt)
{
ll st=l+1;
ll dr=r-1;
if(st<=dr)
{
if(suma(dr)-suma(st-1)<min(v[l],v[r]))
{
if(setik.find({st,dr})==setik.end())
{
setik.insert({st,dr});
update(1,1,n,st,dr,+1);
}
}
else
{
if(setik.find({st,dr})!=setik.end())
{
setik.erase({st,dr});
update(1,1,n,st,dr,-1);
}
}
}
}
}
else
{
int l,r;
cin>>l>>r;
ll rgt=l;
ll st=l;
ll dr=r;
ll S=suma(l-1);
while(st<=dr)
{
ll mij=(st+dr)/2;
prostie a=querydir(0,1,1,n,mij,r);
if(a.maxim+S>0)
{
rgt=mij;
st=mij+1;
}
else
dr=mij-1;
}
rgt--;
ll lft=r;
S=suma(n)-suma(r);
st=l;
dr=r;
while(st<=dr)
{
ll mij=(st+dr)/2;
prostie a=querydir(1,1,1,n,l,mij);
if(a.maxim+S>0)
{
lft=mij;
dr=mij-1;
}
else
st=mij+1;
}
lft++;
if(l<=rgt)
update(1,1,n,l,rgt,+1);
if(lft<=r)
update(1,1,n,lft,r,+1);
date rez=query(1,1,n,l,r);
if(l<=rgt)
update(1,1,n,l,rgt,-1);
if(lft<=r)
update(1,1,n,lft,r,-1);
cout<<rez.cnt<<'\n';
}
}
return 0;
}
