//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
struct segtree_interval{
stack<pii> stk[4*maxn];
bool in (pii &p, int x) {
return p.ff <= x && x <= p.ss;
}
void remove(int cur, int l, int r, int ind, vector<pii> &v) {
if (r <= l) return;
while (stk[cur].size() && in(stk[cur].top(), ind)) {
v.push_back(stk[cur].top());
stk[cur].pop();
}
int m = (l + r) / 2;
if (ind < m) remove(cur*2, l, m, ind, v);
else if (ind > m) remove(cur*2+1, m+1, r, ind, v);
}
void ins(int cur, int l, int r, pii p) {
if (r <= l) return;
int m = (l + r) / 2;
if (in(p, m)) {
stk[cur].push(p);
return;
}
if (m > p.ss) ins(cur*2, l, m, p);
else if (m < p.ff) ins(cur*2+1, m+1, r, p);
}
} inter;
struct segtree_mincnt{
pii seg[4*maxn];
int tag[4*maxn];
void init(int cur, int l, int r) {
if (r <= l) return;
seg[cur].ss = (r - l);
if (r - l == 1) return;
int m = (l + r) / 2;
init(cur*2, l, m), init(cur*2+1, m, r);
}
void push(int cur, int l, int r) {
seg[cur].ff += tag[cur];
if (r - l > 1) {
tag[cur*2] += tag[cur];
tag[cur*2+1] += tag[cur];
}
tag[cur] = 0;
}
void merge(pii &a, pii &b, pii &c) {
a.ff = min(b.ff, c.ff);
a.ss = (b.ff == a.ff ? b.ss : 0) + (c.ff == a.ff ? c.ss : 0);
}
void pull(int cur, int l, int r) {
int m = (l + r) / 2;
push(cur*2, l, m), push(cur*2+1, m, r);
merge(seg[cur], seg[cur*2], seg[cur*2+1]);
}
void modify(int cur, int l, int r, int ql, int qr, int v) {
if (r <= l || ql >= r || qr <= l) return;
push(cur, l, r);
if (ql <= l && qr >= r) {
tag[cur] += v;
return;
}
int m = (l + r) / 2;
modify(cur*2, l, m, ql, qr, v);
modify(cur*2+1, m, r, ql, qr, v);
pull(cur, l, r);
}
pii query(int cur, int l, int r, int ql, int qr) {
if (r <= l || ql >= r || qr <= l) return {inf, 0};
push(cur, l, r);
if (ql <= l && qr >= r) return seg[cur];
int m = (l + r) / 2;
pii ret, vl = query(cur*2, l, m, ql, qr), vr = query(cur*2+1, m, r, ql, qr);
merge(ret, vl, vr);
return ret;
}
} mincnt;
struct segtree{
ll seg[4*maxn], tag[4*maxn];
void init(int cur, int l, int r, ll a[]) {
if (r <= l) return;
if (r - l == 1) {
seg[cur] = a[l];
return;
}
int m = (l + r) / 2;
init(cur*2, l, m, a), init(cur*2+1, m, r, a);
seg[cur] = max(seg[cur*2], seg[cur*2+1]);
}
void push(int cur, int l, int r) {
seg[cur] += tag[cur];
if (r - l > 1) {
tag[cur*2] += tag[cur];
tag[cur*2+1] += tag[cur];
}
tag[cur] = 0;
}
void pull(int cur, int l, int r) {
int m = (l + r) / 2;
push(cur*2, l, m), push(cur*2+1, m, r);
seg[cur] = max(seg[cur*2], seg[cur*2+1]);
}
void modify(int cur, int l, int r, int ql, int qr, ll x) {
if (r <= l || ql >= r || qr <= l) return;
push(cur, l, r);
if (ql <= l && qr >= r) {
tag[cur] += x;
return;
}
int m = (l + r) / 2;
modify(cur*2, l, m, ql, qr, x);
modify(cur*2+1, m, r, ql, qr, x);
pull(cur, l, r);
}
int search(int cur, int l, int r, int ql, int qr, bool type, ll t) {
//type 0: left, 1:right
push(cur, l, r);
if (r <= l || ql >= r || qr <= l || seg[cur] < t) return -1;
if (r - l == 1) return l;
int m = (l + r) / 2;
if (type) {
int vr = search(cur*2+1, m, r, ql, qr, type, t);
if (vr != -1) return vr;
return search(cur*2, l, m, ql, qr, type, t);
} else {
int vl = search(cur*2, l, m, ql, qr, type, t);
if (vl != -1) return vl;
return search(cur*2+1, m, r, ql, qr, type, t);
}
}
ll query(int cur, int l, int r, int x) { //getpnt
if (r <= l) return 0;
push(cur, l, r);
if (r - l == 1) return seg[cur];
int m = (l + r) / 2;
if (x < m) return query(cur*2, l, m, x);
else query(cur*2+1, m, r, x);
}
void print(int cur, int l, int r) {
if (r <= l) return;
push(cur, l, r);
if (r - l == 1) {
debug(seg[cur]);
return;
}
int m = (l + r) / 2;
print(cur*2, l, m);
print(cur*2+1, m, r);
}
} tr, lb, rb;
struct BIT{
ll bit[maxn];
void modify(int ind, ll val) {
ind++;
for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
}
ll query(int ind) {
ll ret = 0;
ind++;
for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
return ret;
}
ll sum(int l, int r) {
return query(r) - query(l-1);
}
} sum;
ll a[maxn];
int main() {
io
int n, q;
cin >> n;
for (int i = 0;i < n;i++) {
cin >> a[i];
sum.modify(i, a[i]);
}
bool ini = 1;
auto check = [&] (int l, int r, ll s) { //stuck in [l, r]
if (r < l) return;
if (ini) s = sum.sum(l, r);
if(!((l && s >= a[l-1]) || (r < n - 1 && s >= a[r+1]))) {
//debug(l, r);
inter.ins(1, 0, n, {l, r});
mincnt.modify(1, 0, n, l, r+1, 1);
}
};
tr.init(1, 0, n, a);
mincnt.init(1, 0, n);
{
ll pref[maxn];
for (int i = 0;i < n;i++) {
pref[i] = a[i] + (i ? pref[i-1] : 0);
lb.modify(1, 0, n, i, i+1, a[i] - (i ? pref[i-1] : 0));
rb.modify(1, 0, n, i, i+1, a[i] + pref[i]);
}
stack<int> stk;
for (int i = 0;i < n;i++) {
while (stk.size() && a[i] >= a[stk.top()]) {
check(stk.top()+1, i-1, 0);
stk.pop();
}
if (stk.size()) check(stk.top()+1, i-1, 0);
else check(0, i-1, 0);
stk.push(i);
}
while (stk.size()) {
check(stk.top()+1, n-1, 0);
stk.pop();
}
}
ini = 0;
cin >> q;
while (q--) {
int type;
cin >> type;
if (type == 1) {
int i, y;
cin >> i >> y;
i--;
ll d = y - a[i];
tr.modify(1, 0, n, i, i+1, d);
lb.modify(1, 0, n, i, i+1, d);
rb.modify(1, 0, n, i, i+1, d);
lb.modify(1, 0, n, i+1, n, -d);
rb.modify(1, 0, n, i, n, d);
sum.modify(i, d);
a[i] = y;
vector<pii> rem;
inter.remove(1, 0, n, i, rem);
inter.remove(1, 0, n, i-1, rem);
inter.remove(1, 0, n, i+1, rem);
for (auto p:rem) {
//debug("rem", p.ff, p.ss);
mincnt.modify(1, 0, n, p.ff, p.ss+1, -1);
}
vector<int> lef, rig;
int cur = i+1;
ll s = a[i];
if (i+1 < n) {
if (a[i+1] < s) s = a[i+1], cur = i+2;
lef.push_back(i+1);
}
while (cur < n) {
int nxt = tr.search(1, 0, n, cur, n, 0, s+1);
if (nxt != -1) {
rig.push_back(nxt-1);
cur = nxt;
s += a[nxt];
} else {
break;
}
}
rig.push_back(n-1);
cur = i-1, s = a[i];
if (i-1 >= 0) {
if (a[i-1] < s) s = a[i-1], cur = i-2;
rig.insert(rig.begin(), i-1);
}
while (cur >= 0) {
int nxt = tr.search(1, 0, n, 0, cur+1, 1, s+1);
if (nxt != -1) {
lef.push_back(nxt+1);
cur = nxt;
s += a[nxt];
} else {
break;
}
}
lef.push_back(0);
lef.resize(int(unique(lef.begin(), lef.end()) - lef.begin()));
rig.resize(int(unique(rig.begin(), rig.end()) - rig.begin()));
vector<ll> ls, rs;
for (int I:lef) ls.push_back(sum.query(I-1));
for (int I:rig) rs.push_back(sum.query(I));
for (int I = 0;I < lef.size();I++) {
for (int j = 0;j < rig.size();j++) {
check(lef[I], rig[j], rs[j] - ls[I]);
}
}
} else {
int l, r;
cin >> l >> r;
l--; //[l, r)
ll suml = -sum.query(l-1)+1, sumr = sum.query(r-1)+1;
int il = lb.search(1, 0, n, l, r, 1, suml);
int ir = rb.search(1, 0, n, l, r, 0, sumr)+1;
if (il != -1) l = il;
if (ir != -1) r = ir;
cout << mincnt.query(1, 0, n, l, r).ss << "\n";
}
}
}
/*
*/
