#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);
// freopen("inp.inp", "r", stdin);
// freopen("out.out", "w", stdout);
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);
SegmentWalk wow(n);
vector<vector<int>> why(n);
auto erase = [&](int ql, int qr) -> vector<array<int, 2>> { // erases all intervals containing [ql, qr), return the set of deleted intervals
vector<array<int, 2>> res;
if (ql < 0 || qr > n) return res;
while (true) {
int l = wow.walk(0, ql + 1, qr - 1, true);
if (l == -1) break;
int r = why[l].back();
res.push_back({l, r});
paint.add(l, r, -1);
why[l].pop_back();
if (why[l].empty()) wow.set(l, 0);
else wow.set(l, why[l].back());
}
return res;
};
auto insert = [&](int l, int r) -> void {
if (find(why[l].begin(), why[l].end(), r) != why[l].end()) return;
auto it = why[l].begin();
while (it != why[l].end() && *it < r) ++it;
why[l].insert(it, r);
wow.set(l, why[l].back());
paint.add(l, r, +1);
};
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 (l != 0 || r != n) insert(l, r);
}
int q;
cin >> q;
while (q--) {
int type;
cin >> type;
if (type == 1) {
int i, x;
cin >> i >> x;
i--;
auto subinsert = [&](int i) -> void {
if (i < 0 || i >= n) return;
for (auto [l, r] : findAllSaturatedIntervals(0, n, i)) insert(l, r);
};
erase(i - 1, i);
erase(i, i + 1);
erase(i + 1, i + 2);
fen.add(i, -a[i] + x);
a[i] = x;
segwalk.set(i, x);
subinsert(i - 1);
subinsert(i);
subinsert(i + 1);
}
if (type == 2) {
int l, r;
cin >> l >> r;
l--;
vector<array<int, 2>> erase0 = erase(l - 1, l + 1);
vector<array<int, 2>> erase1 = erase(r - 1, r + 1);
vector<array<int, 2>> erase2 = erase(l, r);
vector<array<int, 2>> insert0 = findAllSaturatedIntervals(l, r, l);
vector<array<int, 2>> insert1 = findAllSaturatedIntervals(l, r, r - 1);
for (auto [l, r] : insert0) paint.add(l, r, +1);
for (auto [l, r] : insert1) paint.add(l, r, +1);
cout << paint.countZero(l, r) << '\n';
for (auto [l, r] : insert0) paint.add(l, r, -1);
for (auto [l, r] : insert1) paint.add(l, r, -1);
for (auto [l, r] : erase0) insert(l, r);
for (auto [l, r] : erase1) insert(l, r);
for (auto [l, r] : erase2) insert(l, r);
}
}
}
