#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
#define int ll
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define pb push_back
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x ){cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
const int maxn = 1e5+5;
const int inf = 0x3f3f3f3f;
int n,q;
int A[maxn];
namespace VS{ // value seg tree
int mn[maxn*4], tg[maxn*4], cnt[maxn*4];
inline void push(int o, int l, int r) {
if (tg[o]) {
mn[o] += tg[o];
if (l != r) {
tg[o*2] += tg[o];
tg[o*2+1] += tg[o];
}
tg[o] = 0;
}
}
void pull(int o) {
mn[o] = min(mn[o*2], mn[o*2+1]);
cnt[o] = 0;
if (mn[o*2] == mn[o]) cnt[o] += cnt[o*2];
if (mn[o*2+1] == mn[o]) cnt[o] += cnt[o*2+1];
}
void build(int o=1, int l=0, int r=maxn-1){
if (l == r) {
cnt[o] = 1;
if (l < n) {
mn[o] = 0;
}else mn[o] = 1;
return;
}
int mid = (l+r)/2;
build(o*2,l,mid); build(o*2+1,mid+1,r);
pull(o);
}
void MO(int L, int R, int v, int o=1, int l=0, int r=maxn-1) {
push(o,l,r);
if (l > R || r < L) return;
if (l >= L && r <= R) {
tg[o] += v; push(o,l,r); return;
}
int mid = (l+r)/2;
MO(L,R,v,o*2,l,mid); MO(L,R,v,o*2+1,mid+1,r);
pull(o);
}
int QU(int L, int R, int o=1, int l=0, int r=maxn-1) {
if (l > R || r < L) return 0;
push(o,l,r);
if (l >= L && r <= R) {
return mn[o]<=0?cnt[o]:0;
}
int mid = (l+r)/2;
return QU(L,R,o*2,l,mid) + QU(L,R,o*2+1,mid+1,r);
}
};
namespace NXTS{ // next value seg tree
int mx[maxn*4];
void build(int o=1, int l=0, int r=maxn-1){
if (l == r) {
if (l < n) {
mx[o] = A[l];
}else{
mx[o] = inf;
}
return;
}
int mid = (l+r)/2;
build(o*2,l,mid); build(o*2+1,mid+1,r);
mx[o] = max(mx[o*2], mx[o*2+1]);
}
void MO(int p, int v, int o=1, int l=0, int r=maxn-1) {
if (l > p || r < p) return;
if (l == r) {
mx[o] = v; return;
}
int mid = (l+r)/2;
MO(p,v,o*2,l,mid); MO(p,v,o*2+1,mid+1,r);
mx[o] = max(mx[o*2], mx[o*2+1]);
}
int Qright(int L, int R, int v, int o=1, int l=0, int r=maxn-1) { // rightmost point in this range geq than v
if (mx[o] < v || l > R || r < L) return -1;
if (l == r) return l;
int mid = (l+r)/2;
int gr = Qright(L,R,v,o*2+1,mid+1,r);
if (gr == -1) return Qright(L,R,v,o*2,l,mid);
else return gr;
}
int Qleft(int L, int R, int v, int o=1, int l=0, int r=maxn-1) { // rightmost point in this range geq than v
if (mx[o] < v || l > R || r < L) return -1;
if (l == r) return l;
int mid = (l+r)/2;
int gl = Qleft(L,R,v,o*2,l,mid);
if (gl == -1) return Qleft(L,R,v,o*2+1,mid+1,r);
else return gl;
}
};
namespace BIT{
// for range sum only i guess
ll s[maxn];
ll QU(int e) {
ll re = 0; for (++e; e>0; e-=e&-e) re += s[e]; return re;
}
ll QU(int l, int r) {
return QU(r) - QU(l-1);
}
void MO(int e, int v) {
for (++e; e<maxn; e+=e&-e) {
s[e] += v;
}
}
}
int toL[maxn], toR[maxn];
//vector<int> fromL[maxn], fromR[maxn]; // from my left, from my right
void updl(int v) {
if (toL[v]!=-1) {
int p = toL[v];
toL[v] = -1;
VS::MO(p+1, v-1, -1);
bug("bye", v, p);
}
int P = NXTS::Qright(0,v-1,A[v]);
// bug(v,P);
if (P != -1 && P != v-1) {
assert(A[P] >= A[v]);
ll btw = BIT::QU(P+1, v-1);
if (btw < A[v]) {
// yay
VS::MO(P+1, v-1, 1);
toL[v] = P;
bug(btw, v, P);
}
}
}
void updr(int v) {
if (toR[v]!=-1) {
int p = toR[v];
toR[v] = -1;
VS::MO(v+1,p-1, -1);
}
int P = NXTS::Qleft(v+1,n-1,A[v]);
// bug(v,P);
if (P != -1 && P != v+1) {
assert(A[P] >= A[v]);
ll btw = BIT::QU(v+1,P-1);
if (btw < A[v]) {
VS::MO(v+1, P-1, 1);
toR[v] = P;
bug(v, P);
}
}
}
void ptchg(int v, int val) {
BIT::MO(v, val - A[v]); NXTS::MO(v, val);
A[v] = val;
}
void chg(int v, int val, bool doleft, bool doright) {
// walk left!!
ptchg(v,val);
updl(v); updr(v);
if (doleft) {
for (int u = v-1; u!=-1 && u>=0; u = NXTS::Qright(0,u-1,1+BIT::QU(u,v-1))) {
updr(u);
}
}
if (doright) {
for (int u = v+1; u!=-1 && u<n; u = NXTS::Qleft(u+1, maxn-1, 1+BIT::QU(v+1, u))) {
updl(u);
}
}
}
struct mot{
int l,r,v;
};
ll getfast(int l, int r) {
vector<mot > undo;
{
for (int u = l-1; u!=-1 && u>=0; u = NXTS::Qright(0,u-1,1+BIT::QU(u,l-1))) {
if (toR[u] != -1) {
VS::MO(u+1, toR[u]-1, -1);
undo.pb({u+1, toR[u]-1, 1});
bug(u);
}
}
int last = -1;
for (int u = l; u!=-1 && u<=r; u = NXTS::Qleft(u+1, maxn-1, 1+BIT::QU(l, u))) {
if (A[u] > BIT::QU(l,u-1)) {
last = u;
bug(u);
}
}
if (last != -1) {
VS::MO(l, last-1, 1);
undo.pb({l, last-1, -1});
}
}
{
for (int u = r+1; u!=-1 && u<n; u = NXTS::Qleft(u+1,maxn-1,1+BIT::QU(r+1,u))) {
if (toL[u] != -1) {
VS::MO(toL[u]+1, u-1, -1);
undo.pb({toL[u]+1, u-1, 1});
bug(u);
}
}
int last = -1;
for (int u = r; u!=-1 && u>=l; u = NXTS::Qright(0, u-1, 1+BIT::QU(u, r))) {
if (A[u] > BIT::QU(u+1,r)) {
last = u;
}
}
if (last != -1) {
VS::MO(last+1, r, 1);
undo.pb({last+1, r, -1});
// bug(u);
}
}
ll re = VS::QU(l,r);
for (auto e : undo) {
bug(e.l, e.r, e.v);
VS::MO(e.l, e.r, e.v);
}
return re;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
cin>>n;
n+=2;
REP1(i,n-2) {
cin>>A[i];
}
ll big = 1e15+10;
A[0] = A[n-1] = big;
REP(i,n){
BIT::MO(i, A[i]);
}
VS::build(); NXTS::build();
memset(toL, -1, sizeof toL);
memset(toR, -1, sizeof toR);
REP(i,n) {
updl(i); updr(i);
}
cin>>q;
while (q--) {
int tp, l, r; cin>>tp>>l>>r;
if (tp == 2) {
cout<<getfast(l,r)<<endl;
}else{
// ptchg(l,r);
chg(l,r,1,1);
// updl(l); updr(l);
}
}
}
