#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) {
i += N;
g[i] = {x, i};
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], left_[N], right_[N];
void set_up_to(int i, int x) {
if (up[i] != x) {
up[i] = x;
if (!x) {
tadd(left_[i] + 1, right_[i], -1);
} else {
tadd(left_[i] + 1, right_[i], 1);
}
}
}
void loop_set_up(int u, int l, int r, int x, vector<pair<int, int>> &change) {
assert(l <= u && u < r);
auto ai = [&](int i) {
if (i < l || i >= r) {
return +INF;
}
return a[i];
};
int cl = max(left_[u], l - 1), cr = min(right_[u], r);
ll sm = gsum(cl + 1, cr);
// cout << "loop_set_up" << u << " " << l << " " << r << " " << x << endl;
while (cl != l - 1 || cr != r) {
// cout << cl << " " << cr << " " << sm << endl;
if (sm < min(ai(cl), ai(cr))) {
int v = gget(cl + 1, cr).y;
change.push_back({v, x});
// cout << "set up to " << u << " " << x << endl;
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);
// cout << "got new sum " << sm << " " << cl << " " << cr << endl;
sm = gsum(cl + 1, cr);
}
}
int ai(int i) {
if (i < 0 || i >= n) {
return +INF;
}
return a[i];
}
vector<pair<int, int>> 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), [](auto x, auto y) {
return x.x < y.x;
});
change.resize(unique(all(change), [](auto x, auto y) {
return x.x == y.x;
}) - begin(change));
assert(sz(change) < 120);
for (auto &[where, what] : change) {
int backup = up[what];
set_up_to(where, what);
what = backup;
}
auto [ansx, ansy] = tget(l, r);
for (auto [where, what] : change) {
set_up_to(where, what);
}
return ansx ? 0 : ansy;
}
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) {
left_[i] = glastgreater(0, i, a[i]);
right_[i] = gfirstgreater(i + 1, n, a[i] - 1);
if (gsum(left_[i] + 1, right_[i]) < min(ai(left_[i]), ai(right_[i])) &&
(left_[i] != -1 || right_[i] != n)) {
set_up_to(i, 1);
}
}
int queries;
cin >> queries;
while (queries--) {
int type, l, r;
cin >> type >> l >> r;
if (type == 1) {
// a[l - 1] = r;
// gset(l - 1, r);
assert(0);
} else {
cout << query(l - 1, r) << "\n";
}
}
}
