#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;
template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;
const int N = 1 << 17, INF = 0x3f3f3f3f;
pair<int, int> t[2 * N];
int mod[2 * N];
pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
if (a.x == b.x) {
return {a.x, a.y + b.y};
}
return min(a, b);
}
void tapply(int i, int x) {
t[i].x += x;
mod[i] += x;
}
void tpush(int i) {
if (mod[i]) {
tapply(2 * i + 1, mod[i]);
tapply(2 * i + 2, mod[i]);
mod[i] = 0;
}
}
void tpull(int i) {
t[i] = merge(t[2 * i + 1], t[2 * i + 2]);
}
void tadd(int ql, int qr, int x, int ci = 0, int cl = 0, int cr = N) {
if (ql <= cl && cr <= qr) {
tapply(ci, x);
return;
}
if (qr <= cl || cr <= ql) {
return;
}
int mid = (cl + cr) / 2;
tpush(ci);
tadd(ql, qr, x, 2 * ci + 1, cl, mid);
tadd(ql, qr, x, 2 * ci + 2, mid, cr);
tpull(ci);
}
pair<int, int> tget(int ql, int qr, int ci = 0, int cl = 0, int cr = N) {
if (ql <= cl && cr <= qr) {
return t[ci];
}
if (qr <= cl || cr <= ql) {
return {+INF, 0};
}
int mid = (cl + cr) / 2;
tpush(ci);
return merge(
tget(ql, qr, 2 * ci + 1, cl, mid),
tget(ql, qr, 2 * ci + 2, mid, cr)
);
}
pair<int, int> g[2 * N];
ll gs[2 * N];
void gset(int i, int x) {
g[i + N] = {x, i};
i += N;
gs[i] = x;
i /= 2;
while (i) {
g[i] = max(g[2 * i], g[2 * i + 1]);
gs[i] = gs[2 * i] + gs[2 * i + 1];
i /= 2;
}
}
pair<int, int> gget(int l, int r) {
l += N, r += N - 1;
pair<int, int> ans = {-1, -1};
while (l <= r) {
if (l & 1) ans = max(ans, g[l]);
if (!(r & 1)) ans = max(ans, g[r]);
l = (l + 1) / 2;
r = (r - 1) / 2;
}
return ans;
}
ll gsum(int l, int r) {
l += N, r += N - 1;
ll ans = 0;
while (l <= r) {
if (l & 1) ans += gs[l];
if (!(r & 1)) ans += gs[r];
l = (l + 1) / 2;
r = (r - 1) / 2;
}
return ans;
}
int gfirstgreater(int ql, int qr, ll x, int ci = 1, int cl = 0, int cr = N) {
if (qr <= cl || cr <= ql || g[ci].x <= x) {
return qr;
}
if (cr - cl == 1) {
return cl;
}
int mid = (cl + cr) / 2;
int res = gfirstgreater(ql, qr, x, 2 * ci, cl, mid);
if (res >= qr) {
return gfirstgreater(ql, qr, x, 2 * ci + 1, mid, cr);
} else {
return res;
}
}
int glastgreater(int ql, int qr, ll x, int ci = 1, int cl = 0, int cr = N) {
if (qr <= cl || cr <= ql || g[ci].x <= x) {
return ql - 1;
}
if (cr - cl == 1) {
return cl;
}
int mid = (cl + cr) / 2;
int res = glastgreater(ql, qr, x, 2 * ci + 1, mid, cr);
if (res < ql) {
return glastgreater(ql, qr, x, 2 * ci, cl, mid);
} else {
return res;
}
}
int a[N], n;
int up[N];
struct S {
int i, x, cl, cr;
bool operator<(const S &other) const {
return i < other.i;
}
bool operator==(const S &other) const {
return i == other.i && cl == other.cl && cr == other.cr;
}
};
void set_up_to(const S &s) {
if (up[s.i] != s.x) {
up[s.i] = s.x;
// cout << "real tadd " << s.cl + 1 << " " << s.cr << " " << (s.x ? 1 : -1) << endl;
if (!s.x) {
tadd(s.cl + 1, s.cr, -1);
} else {
tadd(s.cl + 1, s.cr, 1);
}
}
}
void loop_set_up(int u, int l, int r, int x, vector<S> &change) {
if (!(l <= u && u < r)) {
return;
}
auto ai = [&](int i) {
if (i < l || i >= r) {
return +INF;
}
return a[i];
};
int cl = glastgreater(l, u, a[u]),
cr = gfirstgreater(u + 1, r, a[u] - 1);
ll sm = gsum(cl + 1, cr);
while (cl != l - 1 || cr != r) {
if (sm < min(ai(cl), ai(cr))) {
int v = gget(cl + 1, cr).y;
// cout << "set " << cl << " " << cr << " " << v << endl;
change.push_back({v, x, cl, cr});
if (ai(cl) <= ai(cr)) {
sm += a[cl];
--cl;
} else {
sm += a[cr];
++cr;
}
}
cl = glastgreater(l, cl + 1, sm);
cr = gfirstgreater(cr - 1, r, sm);
sm = gsum(cl + 1, cr);
}
}
int ai(int i) {
if (i < 0 || i >= n) {
return +INF;
}
return a[i];
}
vector<S> change;
int query(int l, int r) {
change.clear();
if (l) {
loop_set_up(l, 0, n, 0, change);
loop_set_up(l, l, r, 1, change);
}
if (r != n) {
loop_set_up(r - 1, 0, n, 0, change);
loop_set_up(r - 1, l, r, 1, change);
}
stable_sort(all(change));
reverse(all(change));
change.resize(unique(all(change), [](auto x, auto y) {
return x.i == y.i;
}) - begin(change));
for (auto &s : change) {
// cout << "temp " << s.cl << " " << s.cr << " " << s.i << " " << s.x << endl;
int backup = up[s.i];
set_up_to(s);
s.x = backup;
}
auto [ansx, ansy] = tget(l, r);
// cout << ansx << " " << ansy << endl;
for (const auto &s : change) {
set_up_to(s);
}
return ansx ? 0 : ansy;
}
void aset(int i, int x) {
int cl = glastgreater(0, i, a[i]),
cr = gfirstgreater(i + 1, n, a[i] - 1),
nl = glastgreater(0, i, x),
nr = gfirstgreater(i + 1, n, x - 1);
// cout << cr << endl;
int clef = gget(cl + 1, i).y, crig = gget(i + 1, cr).y,
nlef = gget(nl + 1, i).y, nrig = gget(i + 1, nr).y;
// cout << "counted " << clef << " " << crig << " " << nlef << " " << nrig << endl;
change.clear();
loop_set_up(i, 0, n, 0, change);
loop_set_up(cl, 0, n, 0, change);
loop_set_up(cr, 0, n, 0, change);
loop_set_up(clef, 0, n, 0, change);
loop_set_up(crig, 0, n, 0, change);
loop_set_up(nl, 0, n, 0, change);
loop_set_up(nr, 0, n, 0, change);
loop_set_up(nlef, 0, n, 0, change);
loop_set_up(nrig, 0, n, 0, change);
a[i] = x;
gset(i, x);
loop_set_up(i, 0, n, 1, change);
loop_set_up(cl, 0, n, 1, change);
loop_set_up(cr, 0, n, 1, change);
loop_set_up(clef, 0, n, 1, change);
loop_set_up(crig, 0, n, 1, change);
loop_set_up(nl, 0, n, 1, change);
loop_set_up(nr, 0, n, 1, change);
loop_set_up(nlef, 0, n, 1, change);
loop_set_up(nrig, 0, n, 1, change);
stable_sort(all(change));
reverse(all(change));
change.resize(unique(all(change)) - begin(change));
reverse(all(change));
for (auto s : change) {
// cout << "apply " << s.cl << " " << s.cr << " " << s.i << " " << s.x << endl;
set_up_to(s);
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
g[N + i] = {a[i], i};
gs[N + i] = a[i];
}
for (int i = 0; i < n; ++i) {
t[N - 1 + i] = {0, 1};
}
for (int i = N - 1; i--; ) {
t[i] = merge(t[2 * i + 1], t[2 * i + 2]);
mod[i] = 0;
}
for (int i = N; i--; ) {
g[i] = max(g[2 * i], g[2 * i + 1]);
gs[i] = gs[2 * i] + gs[2 * i + 1];
}
for (int i = 0; i < n; ++i) {
int cl = glastgreater(0, i, a[i]);
int cr = gfirstgreater(i + 1, n, a[i] - 1);
if (gsum(cl + 1, cr) < min(ai(cl), ai(cr)) &&
(cl != -1 || cr != n)) {
set_up_to({i, 1, cl, cr});
}
}
int queries;
cin >> queries;
while (queries--) {
int type, l, r;
cin >> type >> l >> r;
if (type == 1) {
aset(l - 1, r);
} else {
cout << query(l - 1, r) << "\n";
}
}
}
