#include <iostream>
#include <map>
#include <array>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
ll n, q, ty, x, y, A[100000], X[100000], ps[100000];
ll listnx[100000][30], listpv[100000][30];
vector <ll> V[30];
struct BIT{
ll bt[100001];
void add(ll id, ll w) {
++id;
while (id <= n) {
bt[id] += w;
id += id & -id;
}
}
ll ask(ll id) {
ll res = 0;
while (id) {
res += bt[id];
id -= id & -id;
}
return res;
}
ll query(ll l, ll r) {
if (l > r) return (ll)1e18;
return ask(r+1) - ask(l);
}
}bit;
array<ll, 2> operator+(array<ll, 2> a, array<ll, 2> b) {
return {a[0] + b[0], a[1] + b[1]};
}
struct SegTree{
array<ll, 2> st[400000];
void update(ll id, ll l, ll r, ll q, array<ll, 2> w) {
if (l == r) {
st[id] = w;
return;
}
ll mid = (l+r)/2;
if (q <= mid) update(id*2, l, mid, q, w);
else update(id*2+1, mid+1, r, q, w);
st[id] = st[id*2] + st[id*2+1];
}
array<ll, 2> query(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql) return {0, 0};
else if (ql <= l && r <= qr) return st[id];
ll mid = (l+r)/2;
return query(id*2, l, mid, ql, qr) + query(id*2+1, mid+1, r, ql, qr);
}
}ST[30];
struct MapSegTree{
ll st[400000];
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = A[l];
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = max(st[id*2], st[id*2+1]);
}
void update(ll id, ll l, ll r, ll q, ll w) {
if (l == r) {
st[id] = w;
return;
}
ll mid = (l+r)/2;
if (q <= mid) update(id*2, l, mid, q, w);
else update(id*2+1, mid+1, r, q, w);
st[id] = max(st[id*2], st[id*2+1]);
}
ll queryL(ll id, ll l, ll r, ll ql, ll qr, ll w) {
if (qr < l || r < ql || st[id] < w) return -1;
else if (ql <= l && r <= qr) {
if (l == r) return l;
ll mid = (l+r)/2;
if (st[id*2] >= w) return queryL(id*2, l, mid, ql, qr, w);
else return queryL(id*2+1, mid+1, r, ql, qr, w);
}
ll mid = (l+r)/2, res = queryL(id*2, l, mid, ql, qr, w);
return (res == -1 ? queryL(id*2+1, mid+1, r, ql, qr, w) : res);
}
ll queryR(ll id, ll l, ll r, ll ql, ll qr, ll w) {
if (qr < l || r < ql || st[id] < w) return -1;
else if (ql <= l && r <= qr) {
if (l == r) return l;
ll mid = (l+r)/2;
if (st[id*2+1] >= w) return queryR(id*2+1, mid+1, r, ql, qr, w);
else return queryR(id*2, l, mid, ql, qr, w);
}
ll mid = (l+r)/2, res = queryR(id*2+1, mid+1, r, ql, qr, w);
return (res == -1 ? queryR(id*2, l, mid, ql, qr, w) : res);
}
}ST2;
ll check(ll j, ll u, ll xl, ll xr) {
ll ql = u, qr = u, v = 1e18;
if (listpv[u][j] != -1) {
ll pv = listpv[u][j];
ql = pv+1;
if (pv >= xl) v = min(v, A[pv]);
}
else ql = 0;
ll nx = listnx[u][j];
if (nx != -1) {
qr = nx-1;
if (nx <= xr) v = min(v, A[nx]);
}
else qr = n-1;
ql = max(ql, xl);
qr = min(qr, xr);
if (bit.query(ql, qr) < v && v != 1e18) return 1;
else return 0;
}
void reconstruct(ll j, ll l, ll r) {
ll ql = l, qr = r-1, v = A[r], tot = 0;
if (j == X[l]-1) tot = check(j, l, (ll)-1e18, (ll)1e18);
array <ll, 2> u = {0, 0};
if (j) u = ST[j-1].query(1, 0, n-1, l, r-1);
if (bit.query(l+1, r-1) < min(A[l], A[r])) {
ST[j].update(1, 0, n-1, l, {r-l-1-u[1]+tot, r-l-1+tot});
}
else {
ST[j].update(1, 0, n-1, l, {tot, u[1]+tot});
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
cin >> n;
for (int i=0; i<n; ++i) {
cin >> A[i];
bit.add(i, A[i]);
ps[i] = A[i] + (i == 0 ? 0 : ps[i-1]);
X[i] = (ll)(log2(A[i]));
for (int j=0; j<X[i]; ++j) V[j].push_back(i);
for (int j=0; j<30; ++j) listnx[i][j] = listpv[i][j] = -1;
}
for (int j=0; j<30; ++j) {
for (int i=0; i+1<V[j].size(); ++i) {
listnx[V[j][i]][j] = V[j][i+1];
listpv[V[j][i+1]][j] = V[j][i];
reconstruct(j, V[j][i], V[j][i+1]);
}
}
ST2.build(1, 0, n-1);
cin >> q;
while (q--) {
cin >> ty >> x >> y;
if (ty == 1) {
--x;
ll z1 = X[x], z2 = (ll)log2(y);
ST2.update(1, 0, n-1, x, y);
bit.add(x, y-A[x]);
A[x] = y, X[x] = z2;
for (int j=0; j<30; ++j) {
ST[j].update(1, 0, n-1, x, {0, 0});
ll it = ST2.queryL(1, 0, n-1, x, n-1, (1<<(j+1)));
listnx[x][j] = listpv[x][j] = -1;
if (it != -1) {
ll pv = ST2.queryR(1, 0, n-1, 0, it-1, (1<<(j+1)));
if (pv != -1) {
listnx[pv][j] = it;
listpv[it][j] = pv;
reconstruct(j, pv, it);
}
else listpv[it][j] = -1;
if (it == x) {
ll nx = ST2.queryL(1, 0, n-1, it+1, n-1, (1<<(j+1)));
if (nx != -1) {
listnx[it][j] = nx;
listpv[nx][j] = it;
reconstruct(j, it, nx);
if (X[nx]-1 == j) {
ll nx2 = ST2.queryL(1, 0, n-1, nx+1, n-1, (1<<(j+1)));
if (nx2 != -1) reconstruct(j, nx, nx2);
}
}
else listnx[it][j] = -1;
}
else if (X[it]-1 == j) {
ll nx2 = ST2.queryL(1, 0, n-1, it+1, n-1, (1<<(j+1)));
if (nx2 != -1) reconstruct(j, it, nx2);
}
}
else {
ll pv = ST2.queryR(1, 0, n-1, 0, x-1, (1<<(j+1)));
if (pv != -1) {
listnx[pv][j] = -1;
ST[j].update(1, 0, n-1, pv, {0, 0});
}
}
}
}
else {
--x, --y;
ll f = y-x+1, nx = x, ny = y;
for (int j=0; j<30; ++j) {
ll it = ST2.queryL(1, 0, n-1, x, n-1, (1LL<<(j+1)));
if (it == -1 || it > y) continue;
ll it2 = ST2.queryR(1, 0, n-1, 0, y, (1LL<<(j+1)));
if (bit.query(x, it-1) < A[it]) nx = it;
if (bit.query(it2+1, y) < A[it2]) ny = it2;
}
f -= nx-x+y-ny;
for (int j=0; j<30; ++j) {
ll it = ST2.queryL(1, 0, n-1, nx, n-1, (1<<(j+1)));
if (it == -1 || it > ny) continue;
ll it2 = ST2.queryR(1, 0, n-1, 0, ny, (1<<(j+1)));
if (it != it2) {
auto u = ST[j].query(1, 0, n-1, it, it2-1);
if (X[it]-1 == j) u[0] += check(j, it, x, y) - check(j, it, (ll)-1e18, (ll)1e18);
f -= u[0];
}
if (X[it2]-1 == j) {
f -= check(j, it2, x, y);
}
}
cout << f << '\n';
}
}
}
