#include <bits/stdc++.h>
using namespace std;
struct node {
int tl, tr;
vector<pair<int, int>> lefts, rights;
int dominators;
node() : dominators(0), tl(-1), tr(-1) {}
node(int tl, int tr) : dominators(0), tl(tl), tr(tr) {}
node(int i) : dominators(1), tl(i), tr(i) {}
};
class fenwick {
int n;
vector<int64_t> bit;
public:
fenwick(int _n) : n(_n + 1), bit(_n + 1) {}
void add(int i, int64_t x) {
for (i += 1; i <= n; i += i & -i) {
bit[i] += x;
}
}
int64_t query(int i) {
int64_t ans = 0;
for (i += 1; i >= 1; i -= i & -i) {
ans += bit[i];
}
return ans;
}
};
// stores agg max
class segment_tree {
int n;
vector<int64_t> seg;
void set(int v, int tl, int tr, int i, int64_t x) {
if (i < tl || tr < i) {
return;
}
if (tl == tr && tl == i) {
seg[v] = x;
return;
}
int tm = (tl + tr) / 2;
set(2 * v, tl, tm, i, x), set(2 * v + 1, tm + 1, tr, i, x);
seg[v] = max(seg[2 * v], seg[2 * v + 1]);
}
template <typename Fn>
int min_right(int v, int tl, int tr, int l, const Fn &f) {
if (tr < l || !f(seg[v])) {
return n;
}
if (tl == tr) {
return tl;
}
int tm = (tl + tr) / 2;
int ans = min_right(2 * v, tl, tm, l, f);
if (ans != n) {
return ans;
}
return min_right(2 * v + 1, tm + 1, tr, l, f);
}
template <typename Fn>
int max_left(int v, int tl, int tr, int r, const Fn &f) {
if (r < tl || !f(seg[v])) {
return -1;
}
if (tl == tr) {
return tl;
}
int tm = (tl + tr) / 2;
int ans = max_left(2 * v + 1, tm + 1, tr, r, f);
if (ans != -1) {
return ans;
}
return max_left(2 * v, tl, tm, r, f);
}
public:
segment_tree(int n) : n(n), seg(4 * n) {}
void set(int i, int64_t x) { set(1, 0, n - 1, i, x); }
template <typename Fn>
int min_right(int l, const Fn &f) { return min_right(1, 0, n - 1, l, f); }
template <typename Fn>
int max_left(int r, const Fn &f) { return max_left(1, 0, n - 1, r, f); }
};
class data_structure {
vector<node> seg;
int n;
vector<int64_t> a;
fenwick fw;
segment_tree st;
int64_t pref(int i) { return i < 0 ? 0 : fw.query(i); }
node merge(const node &left, const node &right) {
if (left.tl == -1) { return right; }
if (right.tl == -1) { return left; }
int tl = left.tl, tr = right.tr, tm = left.tr;
node res(tl, tr);
auto add = [&](int l, int r, int cnt) {
if (l != tl && r != tr) { return; }
if (l == tl && r == tr) {
res.dominators += cnt;
} else if (l == tl) {
res.lefts.push_back({r, cnt});
} else {
res.rights.push_back({l, cnt});
}
};
int cur_l = tm, cur_r = tm;
int64_t cur_sum = a[tm];
auto expand = [&]() {
int changed = 1;
while (changed) {
int _cur_l = cur_l, _cur_r = cur_r;
changed = 0;
if (cur_l > tl) {
int l = max(tl - 1, st.max_left(cur_l - 1, [&](int64_t x) { return x > cur_sum; })) + 1;
cur_sum += pref(cur_l - 1) - pref(l - 1);
cur_l = l;
}
if (cur_r < tr) {
int r = min(tr + 1, st.min_right(cur_r + 1, [&](int64_t x) { return x > cur_sum; })) - 1;
cur_sum += pref(r) - pref(cur_r);
cur_r = r;
}
changed = _cur_l != cur_l || _cur_r != cur_r;
}
};
// expand left suffixes
for (int _ = left.rights.size() - 1; _ >= 0; --_) {
auto [l, cnt] = left.rights[_];
if (l < cur_l) {
cur_sum += pref(cur_l - 1) - pref(l - 1);
cur_l = l;
}
expand();
add(cur_l, cur_r, cnt);
}
// expand right prefixes
cur_l = tm + 1, cur_r = tm + 1, cur_sum = a[tm + 1];
for (auto &[r, cnt] : right.lefts) {
if (cur_r < r) {
cur_sum += pref(r) - pref(cur_r);
cur_r = r;
}
expand();
add(cur_l, cur_r, cnt);
}
// expand left dominators
cur_l = tl, cur_r = tm, cur_sum = pref(tm) - pref(tl - 1);
expand();
add(cur_l, cur_r, left.dominators);
// expand right dominators
cur_l = tm + 1, cur_r = tr, cur_sum = pref(tr) - pref(tm);
expand();
add(cur_l, cur_r, right.dominators);
// add left lefts
for (auto &p : left.lefts) {
res.lefts.push_back(p);
}
// add right rights
for (auto &p : right.rights) {
res.rights.push_back(p);
}
ranges::sort(res.lefts);
ranges::sort(res.rights);
auto dupes = [&](vector<pair<int, int>> &v) {
vector<pair<int, int>> res;
for (auto &[x, cnt] : v) {
if (!res.empty() && res.back().first == x) {
res.back().second += cnt;
} else {
res.emplace_back(x, cnt);
}
}
v = res;
};
dupes(res.lefts);
dupes(res.rights);
return res;
}
public:
data_structure(int n, vector<int64_t> a) : a(a), fw(n), n(n), seg(2 * n), st(n) {
for (int i = 0; i < n; ++i) {
seg[i + n] = node{i};
fw.add(i, a[i]), st.set(i, a[i]);
}
for (int i = n - 1; i >= 1; --i) {
seg[i] = merge(seg[2 * i], seg[2 * i + 1]);
}
}
void set(int i, int x) {
fw.add(i, -a[i]);
a[i] = x;
fw.add(i, a[i]), st.set(i, a[i]);
for (i += n, i >>= 1; i > 0; i >>= 1) {
seg[i] = merge(seg[2 * i], seg[2 * i + 1]);
}
}
int query(int l, int r) {
node ansL, ansR;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) ansL = merge(ansL, seg[l++]);
if (r & 1) ansR = merge(seg[--r], ansR);
}
return merge(ansL, ansR).dominators;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
vector<int64_t> a(n);
for (int64_t &i : a) {
cin >> i;
}
int first = 1;
while (popcount(unsigned(n)) != 1) {
n++;
a.push_back(first ? int64_t(1e15) : int64_t(1));
first = 0;
}
data_structure ds(n, a);
int q;
cin >> q;
while (q--) {
int t;
cin >> t;
if (t == 1) {
int x, y;
cin >> x >> y;
ds.set(x - 1, y);
} else {
int l, r;
cin >> l >> r;
cout << ds.query(l - 1, r - 1) << '\n';
}
}
}
