#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> B;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=100100;
const int M=8*N;
const int inf=(int)1e9;
int n,q,a[N];
namespace sum {
ll c[N];
void modify(int p,int v) {
for (;p<N;p+=p&-p) c[p]+=v;
}
ll get(int p) {
ll r=0;
for (;p>0;p-=p&-p) r+=c[p];
return r;
}
ll get(int l,int r) {
if (l>r) {
return 0ll;
}
return get(r)-get(l-1);
}
};
namespace cnt {
PII st[M];
int lzy[M];
void push(int x) {
st[x*2].fi+=lzy[x];
st[x*2+1].fi+=lzy[x];
lzy[x*2]+=lzy[x];
lzy[x*2+1]+=lzy[x];
lzy[x]=0;
}
PII mrg(PII a,PII b) {
PII r;
r.fi=min(a.fi,b.fi);
r.se=(a.fi==r.fi?a.se:0)+(b.fi==r.fi?b.se:0);
return r;
}
void pull(int x) {
st[x]=mrg(st[x*2],st[x*2+1]);
}
void build(int x,int l,int r) {
if (l==r) {
st[x].fi=0;
st[x].se=1;
return;
}
int mid=l+r>>1;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
pull(x);
}
void add(int x,int l,int r,int ql,int qr,int v) {
if (l>r||l>qr||r<ql||ql>qr) {
return;
}
if (ql<=l&&r<=qr) {
st[x].fi+=v;
lzy[x]+=v;
push(x);
return;
}
push(x);
int mid=l+r>>1;
add(x*2,l,mid,ql,qr,v);
add(x*2+1,mid+1,r,ql,qr,v);
pull(x);
}
PII query(int x,int l,int r,int ql,int qr) {
if (l>r||l>qr||r<ql) {
return mp(inf,0);
}
if (ql<=l&&r<=qr) {
return st[x];
}
push(x);
int mid=l+r>>1;
auto qvl=query(x*2,l,mid,ql,qr);
auto qvr=query(x*2+1,mid+1,r,ql,qr);
pull(x);
return mrg(qvl,qvr);
}
int sol(int l,int r) {
auto p=query(1,1,n,l,r);
return p.se;
}
};
vector<PII> my;
namespace segs {
vector<PII> st[M];
multiset<PII> all;
void add(int x,int l,int r,int ql,int qr,PII p) {
if (x==1) all.insert(p);
if (l>r||l>qr||r<ql) {
return;
}
if (ql<=l&&r<=qr) {
st[x].pb(p);
return;
}
int mid=l+r>>1;
add(x*2,l,mid,ql,qr,p);
add(x*2+1,mid+1,r,ql,qr,p);
}
/* void rem(int x,int l,int r,PII p) {
if (l>r||l>p.se||r<p.fi) {
return;
}
if (p.fi<=l&&r<=p.se) {
st[x].erase(st[x].find(p));
return;
}
int mid=l+r>>1;
rem(x*2,l,mid,p);
rem(x*2+1,mid+1,r,p);
} */
void dfs(int x,int l,int r,int p) {
for (auto& p:st[x]) {
if (all.find(p)!=all.end()) {
all.erase(all.find(p));
cnt::add(1,1,n,p.fi+1,p.se-1,-1);
}
}
st[x].clear();
if (l==r) {
return;
}
int mid=l+r>>1;
if (p<=mid) {
dfs(x*2,l,mid,p);
} else {
dfs(x*2+1,mid+1,r,p);
}
}
};
namespace pref {
struct node {
ll vl,vr,lzyl,lzyr;
node(ll _vl=0,ll _vr=0,ll tg1=0,ll tg2=0) : vl(_vl),vr(_vr),lzyl(tg1),lzyr(tg2) {}
};
node st[M];
node mrg(node a,node b) {
node r;
r.vl=max(a.vl,b.vl);
r.vr=max(a.vr,b.vr);
return r;
}
void pull(int x) {
st[x]=mrg(st[x*2],st[x*2+1]);
}
void push(int x) {
st[x*2].vl+=st[x].lzyl;
st[x*2+1].vl+=st[x].lzyl;
st[x*2].lzyl+=st[x].lzyl;
st[x*2+1].lzyl+=st[x].lzyl;
st[x].lzyl=0;
st[x*2].vr+=st[x].lzyr;
st[x*2+1].vr+=st[x].lzyr;
st[x*2].lzyr+=st[x].lzyr;
st[x*2+1].lzyr+=st[x].lzyr;
st[x].lzyr=0;
}
void build(int x,int l,int r) {
if (l==r) {
st[x].vl=a[l]-sum::get(1,l-1);
st[x].vr=a[l]-sum::get(l+1,N-1);
st[x].lzyl=0;
st[x].lzyr=0;
return;
}
int mid=l+r>>1;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
pull(x);
}
void modifyL(int x,int l,int r,int ql,int qr,ll v) {
if (l>r||l>qr||r<ql||ql>qr) {
return;
}
if (ql<=l&&r<=qr) {
st[x].lzyl+=v;
st[x].vl+=v;
push(x);
return;
}
push(x);
int mid=l+r>>1;
modifyL(x*2,l,mid,ql,qr,v);
modifyL(x*2+1,mid+1,r,ql,qr,v);
pull(x);
}
void modifyR(int x,int l,int r,int ql,int qr,ll v) {
if (l>r||l>qr||r<ql||ql>qr) {
return;
}
if (ql<=l&&r<=qr) {
st[x].lzyr+=v;
st[x].vr+=v;
push(x);
return;
}
push(x);
int mid=l+r>>1;
modifyR(x*2,l,mid,ql,qr,v);
modifyR(x*2+1,mid+1,r,ql,qr,v);
pull(x);
}
node query(int x,int l,int r,int ql,int qr) {
if (l>r||l>qr||r<ql||ql>qr) {
return node(-inf*1ll*inf,-inf*1ll*inf,0ll,0ll);
}
if (ql<=l&&r<=qr) {
return st[x];
}
push(x);
int mid=l+r>>1;
node qvl=query(x*2,l,mid,ql,qr);
node qvr=query(x*2+1,mid+1,r,ql,qr);
pull(x);
return mrg(qvl,qvr);
}
int walkL(int x,int l,int r,int ql,int qr,ll ft) {
if (l>qr||st[x].vr+ft<=0) return -1;
if (l==r) {
return l;
}
push(x);
int res=-1;
int mid=l+r>>1;
if (r<=qr) {
if (st[x*2+1].vr+ft>0) res=walkL(x*2+1,mid+1,r,ql,qr,ft);
else res=walkL(x*2,l,mid,ql,qr,ft);
} else {
res=walkL(x*2+1,mid+1,r,ql,qr,ft);
if (res==-1) {
res=walkL(x*2,l,mid,ql,qr,ft);
}
}
pull(x);
return res;
}
int walkR(int x,int l,int r,int ql,int qr,ll ft) {
if (r<ql||st[x].vl+ft<=0) return -1;
if (l==r) {
return l;
}
push(x);
int res=-1;
int mid=l+r>>1;
if (l>=ql) {
if (st[x*2].vl+ft>0) res=walkR(x*2,l,mid,ql,qr,ft);
else res=walkR(x*2+1,mid+1,r,ql,qr,ft);
} else {
res=walkR(x*2,l,mid,ql,qr,ft);
if (res==-1) {
res=walkR(x*2+1,mid+1,r,ql,qr,ft);
}
}
pull(x);
return res;
}
};
void build() {
cnt::build(1,1,n);
rep(i,1,n+1) {
sum::modify(i,a[i]);
}
pref::build(1,1,n);
stack<int> stk;
rep(i,1,n+1) {
while (SZ(stk)>0&&a[i]>a[stk.top()]) {
int L=stk.top();
int R=i;
if (L!=R-1&&min(a[L],a[R])>sum::get(L+1,R-1)) {
segs::add(1,1,n,L,R,mp(L,R));
cnt::add(1,1,n,L+1,R-1,1);
}
stk.pop();
}
stk.push(i);
}
while (SZ(stk)) stk.pop();
per(i,1,n+1) {
while (SZ(stk)>0&&a[i]>=a[stk.top()]) {
int L=i;
int R=stk.top();
if (L!=R-1&&min(a[L],a[R])>sum::get(L+1,R-1)) {
segs::add(1,1,n,L,R,mp(L,R));
cnt::add(1,1,n,L+1,R-1,1);
}
stk.pop();
}
stk.push(i);
}
}
int main() {
scanf("%d",&n);
rep(i,1,n+1) {
scanf("%d",&a[i]);
}
build();
scanf("%d",&q);
while (q--) {
int op;
scanf("%d",&op);
if (op==1) {
int i,x;
scanf("%d%d",&i,&x);
sum::modify(i,-a[i]);
sum::modify(i,x);
pref::modifyL(1,1,n,i,i,-a[i]+x);
pref::modifyR(1,1,n,i,i,-a[i]+x);
if (i!=n) pref::modifyL(1,1,n,i+1,n,a[i]-x);
if (i!=1) pref::modifyR(1,1,n,1,i-1,a[i]-x);
a[i]=x;
my.clear();
segs::dfs(1,1,n,i);
for (auto& p:my) {
if (min(a[p.fi],a[p.se])>sum::get(p.fi+1,p.se-1)) {
segs::add(1,1,n,p.fi,p.se,p);
cnt::add(1,1,n,p.fi+1,p.se-1,1);
}
}
VI L(1,i),R(1,i);
{
ll ft=sum::get(i,n);
int cur=i-1;
while (cur>0&&pref::query(1,1,n,1,cur).vr+ft>0) {
int pos=pref::walkL(1,1,n,1,cur,ft);
/* int low=1,high=cur,pos=cur;
while (low<=high) {
int mid=low+high>>1;
if (pref::query(1,1,n,mid,cur).vr+ft>0) {
pos=mid;
low=mid+1;
} else {
high=mid-1;
}
} */
L.pb(pos);
cur=pos-1;
}
}
{
ll ft=sum::get(1,i);
int cur=i+1;
while (cur<=n&&pref::query(1,1,n,cur,n).vl+ft>0) {
int pos=pref::walkR(1,1,n,cur,n,ft);
/* int low=cur,high=n,pos=cur;
while (low<=high) {
int mid=low+high>>1;
if (pref::query(1,1,n,cur,mid).vl+ft>0) {
pos=mid;
high=mid-1;
} else {
low=mid+1;
}
} */
R.pb(pos);
cur=pos+1;
}
}
//rep(j,1,i) if (a[j]>sum::get(j+1,i-1)) L.pb(j);
//rep(j,i+1,n+1) if (a[j]>sum::get(i+1,j-1)) R.pb(j);
for (int x:L) {
for (int y:R) {
if (x+1<y&&min(a[x],a[y])>sum::get(x+1,y-1)) {
segs::add(1,1,n,x,y,mp(x,y));
cnt::add(1,1,n,x+1,y-1,1);
}
}
}
} else {
int l,r;
scanf("%d%d",&l,&r);
{
int low=l,high=r,pos=l;
while (low<=high) {
int mid=low+high>>1;
if (pref::query(1,1,n,mid,r).vl+sum::get(1,l-1)>0) {
pos=mid;
low=mid+1;
} else {
high=mid-1;
}
}
l=pos;
}
{
int low=l,high=r,pos=r;
while (low<=high) {
int mid=low+high>>1;
if (pref::query(1,1,n,l,mid).vr+sum::get(r+1,n)>0) {
pos=mid;
high=mid-1;
} else {
low=mid+1;
}
}
r=pos;
}
//printf("-- %d %d --\n",l,r);
printf("%d\n",cnt::sol(l,r));
}
}
}
