#include <bits/stdc++.h>
using namespace std;
struct Paint {
struct Node {
int mn, cnt;
int lazy = 0;
void add(int delta) {
mn += delta;
lazy += delta;
}
void merge(Node a, Node b) {
mn = min(a.mn, b.mn);
cnt = 0;
if (a.mn == mn) cnt += a.cnt;
if (b.mn == mn) cnt += b.cnt;
}
};
int n;
vector<Node> nodes;
Paint(int n) : n(n), nodes(4 * n) {
auto dfs = [&](auto self, int idx, int l, int r) -> void {
if (l + 1 == r) {
nodes[idx].mn = 0;
nodes[idx].cnt = 1;
} else {
int m = (l + r) >> 1;
self(self, 2 * idx + 1, l, m);
self(self, 2 * idx + 2, m, r);
nodes[idx].merge(nodes[2 * idx + 1], nodes[2 * idx + 2]);
}
};
dfs(dfs, 0, 0, n);
}
void down(int idx) {
nodes[2 * idx + 1].add(nodes[idx].lazy);
nodes[2 * idx + 2].add(nodes[idx].lazy);
nodes[idx].lazy = 0;
}
void add(int ql, int qr, int delta) {
auto dfs = [&](auto self, int idx, int l, int r) -> void {
if (r <= ql || qr <= l) return;
if (ql <= l && r <= qr) return nodes[idx].add(delta);
down(idx);
int m = (l + r) >> 1;
self(self, 2 * idx + 1, l, m);
self(self, 2 * idx + 2, m, r);
nodes[idx].merge(nodes[2 * idx + 1], nodes[2 * idx + 2]);
};
dfs(dfs, 0, 0, n);
}
int countZero(int ql, int qr) {
int fetch = 0;
auto dfs = [&](auto self, int idx, int l, int r) -> void {
if (r <= ql || qr <= l) return;
if (ql <= l && r <= qr) {
fetch += nodes[idx].mn == 0 ? nodes[idx].cnt : 0;
return;
}
down(idx);
int m = (l + r) >> 1;
self(self, 2 * idx + 1, l, m);
self(self, 2 * idx + 2, m, r);
};
dfs(dfs, 0, 0, n);
return fetch;
}
};
struct SegmentWalk {
int n;
vector<int> mx;
SegmentWalk(int n) : n(n), mx(4 * n, 0) {}
void set(int i, int val) {
auto dfs = [&](auto self, int idx, int l, int r) -> void {
if (l + 1 == r) {
mx[idx] = val;
} else {
int m = (l + r) >> 1;
if (i < m) self(self, 2 * idx + 1, l, m);
else self(self, 2 * idx + 2, m, r);
mx[idx] = max(mx[2 * idx + 1], mx[2 * idx + 2]);
}
};
dfs(dfs, 0, 0, n);
}
int walk(int ql, int qr, long long bound, bool request_leftmost) { // in [ql, qr), returns the leftmost (rightmost) position with value > 'bound'
auto dfs = [&](auto self, int idx, int l, int r) -> int {
if (r <= ql || qr <= l || mx[idx] <= bound) return -1;
if (ql <= l && r <= qr) {
while (l + 1 < r) {
int m = (l + r) >> 1;
if (request_leftmost) {
if (mx[2 * idx + 1] > bound) idx = 2 * idx + 1, r = m;
else idx = 2 * idx + 2, l = m;
} else {
if (mx[2 * idx + 2] > bound) idx = 2 * idx + 2, l = m;
else idx = 2 * idx + 1, r = m;
}
}
return l;
}
int m = (l + r) >> 1;
if (request_leftmost) {
int get = self(self, 2 * idx + 1, l, m);
if (get != -1) return get;
return self(self, 2 * idx + 2, m, r);
} else {
int get = self(self, 2 * idx + 2, m, r);
if (get != -1) return get;
return self(self, 2 * idx + 1, l, m);
}
};
return dfs(dfs, 0, 0, n);
}
};
struct Fenwick {
int n;
vector<long long> bit;
Fenwick(int n) : n(n), bit(n + 1, 0) {}
void add(int i, int delta) {
for (i++; i <= n; i += i & -i) bit[i] += delta;
}
long long sum(int i) {
long long res = 0;
for (; i > 0; i -= i & -i) res += bit[i];
return res;
}
long long sum(int l, int r) {
return sum(r) - sum(l);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
Fenwick fen(n);
SegmentWalk segwalk(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
fen.add(i, a[i]);
segwalk.set(i, a[i]);
}
auto findSaturatedInterval = [&](int ql, int qr, int &l, int &r, long long &sum) -> void { // O(log^2), find the tightest saturated interval (or [l, r)) containing the initial interval [l, r)
while (ql < l || r < qr) {
long long old_sum = sum;
if (ql < l) {
int p = segwalk.walk(ql, l, sum, false);
if (p == -1) {
sum += fen.sum(ql, l);
l = ql;
} else {
sum += fen.sum(p + 1, l);
l = p + 1;
if (sum >= a[p]) {
sum += a[p];
l = p;
}
}
}
if (r < qr) {
int p = segwalk.walk(r, qr, sum, true);
if (p == -1) {
sum += fen.sum(r, qr);
r = qr;
} else {
sum += fen.sum(r, p);
r = p;
if (sum >= a[p]) {
sum += a[p];
r = p + 1;
}
}
}
if (sum == old_sum) break;
}
};
auto findAllSaturatedIntervals = [&](int ql, int qr, int i) -> vector<array<int, 2>> { // O(log^2), find all saturated intervals containing i
vector<array<int, 2>> res;
int l = i, r = i + 1;
long long sum = a[i];
while (true) {
findSaturatedInterval(ql, qr, l, r, sum);
if (l == ql && r == qr) break;
res.push_back({l, r});
if (l == ql || (r < qr && a[r] <= a[l - 1])) {
sum += a[r];
r = r + 1;
} else {
sum += a[l - 1];
l = l - 1;
}
}
return res;
};
Paint paint(n);
set<array<int, 2>> saturated_intervals;
for (int i = 0; i < n; i++) {
int l = i, r = i + 1;
long long sum = a[i];
findSaturatedInterval(0, n, l, r, sum);
if (array<int, 2>{l, r} != array<int, 2>{0, n}) {
if (!saturated_intervals.count({l, r})) {
saturated_intervals.insert({l, r});
paint.add(l, r, +1);
}
}
}
int q;
cin >> q;
while (q--) {
int type;
cin >> type;
if (type == 1) {
int i, x;
cin >> i >> x;
i--;
fen.add(i, -a[i] + x);
a[i] = x;
segwalk.set(i, x);
auto erase = [&](int i) { // erase from paint all intervals containing i
if (i < 0 || i >= n) return;
while (!saturated_intervals.empty()) {
auto it = saturated_intervals.lower_bound(array<int, 2>{i + 1, -1});
if (it == saturated_intervals.begin()) break;
--it;
auto [l, r] = *it;
if (r <= i) break;
saturated_intervals.erase(it);
paint.add(l, r, -1);
}
};
auto add = [&](int i) { // add to paint all intervals containing i
if (i < 0 || i >= n) return;
vector<array<int, 2>> fetch = findAllSaturatedIntervals(0, n, i);
for (auto [l, r] : fetch) {
if (!saturated_intervals.count({l, r})) {
saturated_intervals.insert({l, r});
paint.add(l, r, +1);
}
}
};
erase(i);
erase(i - 1);
erase(i + 1);
add(i);
add(i - 1);
add(i + 1);
}
if (type == 2) {
int l, r;
cin >> l >> r;
l--;
// assumes l = 0 and r = n (subtask 5)
cout << paint.countZero(0, n) << '\n';
}
}
}
