//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<"cuuuuuuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
void phongbeo();
const int inf=1e18;
const int mod2=1e9+7;
const int mod1=998244353;
struct icd
{
int a,b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a,b,c;
};
struct id
{
int a,b,c,d;
};
struct ie
{
int a,b,c, d,e,f;
};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int i,s10,s12;
int el=29;
int sa,sb;
main()
{
#ifndef ONLINE_JUDGE
// fin(task),fou(task);
#endif
NHP
/// cin>>s1;
// modwwe
phongbeo(),down
}
struct IT
{
int sl,sr;/// size left
/// size right
ic cr[32];
ic cl[32];
int c,d;
int a;
} t[400001],ans;
int a[100001];
vector<id> v;
bool cmp(id a,id b)
{
return a.a<b.a;
}
IT mer(int y,int z,int mid,int l,int r)
{
IT tx;
v.clear();
for(int i=0; i<=t[z].sl; i++)
v.pb({a[t[z].cl[i].b]-t[z].cl[i].a,t[z].cl[i].a,t[z].cl[i].b,i});
sort(v.begin(),v.end(),cmp);
s4=-1 ;
mx=t[y].sr+1;
s5=-1;
s6=-1;
for(auto x:v )
{
while(mx>0&&t[y].cr[mx-1].a<x.a)s5=max(s5,a[t[y].cr[mx-1].b]-t[y].cr[mx-1].a),mx--;
if(s5>x.b)
{
s4=max(s4,x.c);
if(s4==x.c)
s6=x.d;
}
}
tx.d=t[z].d;
s9=t[z].d;
if(s4!=-1) tx.d+=s4-mid-t[z].cl[s6].c-1,s9+=s4-mid-t[z].cl[s6].c-1;
s10=s4;
v.clear() ;
for(int i=0; i<=t[y].sr; i++)
v.pb({a[t[y].cr[i].b]-t[y].cr[i].a,t[y].cr[i].a,t[y].cr[i].b,i});
sort(v.begin(),v.end(),cmp);
s4=n+1;
mx=-1;
s5=-1;
s6=0;
for(auto x:v)
{
while(mx<t[z].sl&&t[z].cl[mx+1].a<x.a)
mx++,s5=max(s5,a[t[z].cl[mx].b]-t[z].cl[mx].a);
if(s5>x.b)
{
s4=min(s4,x.c);
if(s4==x.c) s6=x.d;
}
}
s8=t[y].d;
tx.d+=t[y].d;
if(s4!=n+1)tx.d+=mid-s4-t[y].cr[s6].c,s8+=mid-s4-t[y].cr[s6].c;
bool dl=0;
bool dr=0;
dem=-1;
for(int i=0; i<=t[y].sl; i++)
tx.cl[++dem]=t[y].cl[i];
sa=-1;
for(int i=0; i<=t[z].sl; i++)
if(t[z].cl[i].a+t[y].a<a[t[z].cl[i].b])
{
tx.cl[++dem]=t[z].cl[i],
dl=1;
if(s10!=-1)
{
if(t[z].cl[i].b<s10)
{
tx.cl[dem].c=t[z].cl[i].b-mid;
}
else tx.cl[dem].c+=s9-t[z].d;
}
tx.cl[dem].c+=s8;
tx.cl[dem].a+=t[y].a;
}
sa=dem;
//if(l==1&&r==3)cout<<t[y].d,down
tx.sl=dem;
dem=-1;
sb=n+1;
for(int i=0; i<=t[y].sr; i++)
if(t[y].cr[i].a+t[z].a<a[t[y].cr[i].b])
{
tx.cr[++dem]=t[y].cr[i],
tx.cr[dem].a+=t[z].a,
dr=1;
if(s4!=n+1)
{
if(s4<t[y].cr[i].b)tx.cr[dem].c=mid-t[y].cr[i].b+1;
else tx.cr[dem].c+=s8-t[y].d;
}
tx.cr[dem].c+=s9;
}
for(int i=0; i<=t[z].sr; i++)
tx.cr[++dem]=t[z].cr[i];
sb=0;
tx.c=s9-tx.cl[sa].c+tx.cl[sa].b-l;
tx.c+=s8-tx.cr[sb].c+r-tx.cr[sb].b;
tx.a=t[y].a+t[z].a;
tx.sr=dem;
return tx;
}
void build(int node,int l,int r)
{
if(l==r)
{
t[node].cr[0]=t[node].cl[0]= {0,l};
t[node].a=a[l];
return;
}
int mid=l+r>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
t[node]=mer(node<<1,node<<1|1,mid,l,r);
}
void upd(int node,int l,int r,int l1)
{
if(l==r)
{
t[node].cr[0]=t[node].cl[0]= {0,l};
t[node].a=a[l];
return;
}
int mid=l+r>>1;
if(l1<=mid) upd(node<<1,l,mid,l1);
else upd(node<<1|1,mid+1,r,l1);
t[node]=mer(node<<1,node<<1|1,mid,l,r);
}
void get(int node,int l,int r, int l1,int r1)
{
if(l>r1||r<l1) return ;
if(l>=l1&&r<=r1)
{
if(l==l1) t[0]=t[node];
else t[0]=mer(0,node,l-1,l1,r);
return;
}
int mid=l+r>>1;
get(node<<1,l,mid,l1,r1);
get(node<<1|1,mid+1,r,l1,r1);
}
void phongbeo()
{
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
build(1,1,n);
cin>>m;
for(int i=1; i<=m; i++)
{
cin>>l;
if(l==1)
{
cin>>l>>r;
a[l]=r;
upd(1,1,n,l);
}
else
{
t[0].sl=-1;
t[0].sr=-1;
cin>>l>>r;
get(1,1,n,l,r);
cout<<r-l+1-t[0].c,down
}
}
}
