#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1e5 + 12, MOD = 998244353;
#define int ll
int n, q;
set<pair<int, int>> s[N], x[N], y[N];
ll a[N], t[N];
const ll inf = (ll)1e15;
void upd(int pos, ll val) {
while(pos <= n) {
t[pos] += val;
pos += pos & -pos;
}
}
ll get(int i) {
ll ret = 0;
while(i) {
ret += t[i];
i -= i & -i;
}
return ret;
}
ll get(int l, int r) {
if(l > r) return 0;
return get(r) - get(l - 1);
}
struct segtree{
vector<ll> t, mod;
void init() {
t.resize(N * 4 + 1, 0);
mod.resize(N * 4 + 1, 0);
}
void inc(int v, ll val) {
mod[v] += val;
t[v] += val;
}
void push(int v) {
if(mod[v]) {
inc(v + v, mod[v]);
inc(v + v + 1, mod[v]);
mod[v] = 0;
}
}
void upd(int l, int r, ll val, int v, int tl, int tr) {
if(l > r || tl > r || l > tr) return;
if(tl >= l && tr <= r) {
// cout << t[v] << "x\n";
inc(v, val);
// cout << t[v] << "x\n";
} else {
push(v);
int tm = (tl + tr) >> 1;
upd(l, r, val, v + v, tl, tm);
upd(l, r, val, v + v + 1, tm + 1, tr);
t[v] = max(t[v + v], t[v + v + 1]);
}
// cout << tl << ' ' << tr << ' ' << t[v] << '\n';
}
void upd1(int pos, ll val, int v, int tl, int tr) {
if(tl == tr) {
t[v] = val;
} else {
push(v);
int tm = (tl + tr) >> 1;
if(pos <= tm) upd1(pos, val, v + v, tl, tm);
else upd1(pos, val, v + v + 1, tm + 1, tr);
t[v] = max(t[v + v], t[v + v + 1]);
}
}
ll get(int l, int r, int v, int tl, int tr) {
if(l > r || tl > r || l > tr) return -(ll)1e18;
if(tl >= l && tr <= r) return t[v];
push(v);
int tm = (tl + tr) >> 1;
return max(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}
}tr1, tr2;
int getl(int l, int r) {
if(l == 1) return 0;
ll s = get(l, r);
for(int i = l - 1; i >= 1; i--) {
s += a[i];
if(a[i - 1] > s) {
return i;
}
}
return 1;
}
int getr(int l, int r) {
if(r == n) return n + 1;
ll s = get(l, r), F = get(l - 1);
int L = r, R = n;
while(R - L > 1) {
int mid = (L + R) >> 1;
if(tr1.get(r + 1, mid, 1, 1, n) > -F) {
R = mid;
} else {
L = mid;
}
}
return R;
for(int i = r + 1; i <= n; i++) {
s += a[i];
if(a[i + 1] > s) {
assert(tr1.get(i, i, 1, 1, n) > -F);
if(R != i) {
for(int f = 1; f <= n; f++) {
cout << a[f] << ' ';
}
cout << '\n';
cout << l << ' ' << r << ' ' << R << ' ' << i << '\n';
cout << -F << ' ' << tr1.get(R, R, 1, 1, n) << '\n';
exit(0);
}
return i;
} else {
// assert(tr1.get(i, i, 1, 1, n) <= -F);
}
}
return n;
}
pair<int, int> f[N * 4];
int mod[N * 4];
int sum = 0;
void inc(int v, int val) {
f[v].first += val;
mod[v] += val;
}
void push(int v) {
if(mod[v]) {
inc(v + v, mod[v]);
inc(v + v + 1, mod[v]);
mod[v] = 0;
}
}
pair<int, int> merge(pair<int, int> x, pair<int, int> y) {
if(x.first == y.first) {
x.second += y.second;
}
if(x.first <= y.first) return x;
return y;
}
void upd1(int l, int r, int val, int v = 1, int tl = 1, int tr = n) {
if(l > r || tl > r || l > tr) return ;
if(tl >= l && tr <= r) {
inc(v, val);
} else {
push(v);
int tm = (tl + tr) >> 1;
upd1(l, r, val, v + v, tl, tm);
upd1(l, r, val, v + v + 1, tm + 1, tr);
f[v] = merge(f[v + v], f[v + v + 1]);
}
}
void build(int v = 1, int tl = 1, int tr = n) {
f[v] = {0, tr - tl + 1};
if(tl == tr) return;
int tm = (tl + tr) >> 1;
build(v + v, tl, tm);
build(v + v + 1, tm + 1, tr);
}
pair<int, int> get1(int l, int r, int v = 1, int tl = 1, int tr = n) {
if(l > r || tl > r || l > tr) return {(int)1e9, 0};
if(tl >= l && tr <= r) return f[v];
push(v);
int tm = (tl + tr) >> 1;
return merge(get1(l, r, v + v, tl, tm), get1(l, r, v + v + 1, tm + 1, tr));
}
void add(int l, int r) {
sum += (r - l + 1);
upd1(l, r, 1);
for(int i = l; i <= r; i++) {
s[i].insert({l, r});
}
x[l - 1].insert({l, r});
y[r + 1].insert({l, r});
}
void del(int l, int r) {
upd1(l, r, -1);
for(int i = l; i <= r; i++) {
s[i].erase({l, r});
}
x[l - 1].erase({l, r});
y[r + 1].erase({l, r});
}
void prec() {
for(int i = 1; i <= n; i++) {
upd(i, a[i]);
}
for(int i = 0; i <= n; i++) {
int r = getr(i + 1, i);
while(r <= n) {
if(get(i + 1, r) < a[i]) {
add(i + 1, r);
} else break;
r = getr(i + 1, r);
}
}
}
void u(int l, ll r) {
vector<pair<int, int>> dd;
auto _add = [&](set<pair<int, int>> &st) {
for(auto [l, r] : st) {
dd.emplace_back(l, r);
}
};
_add(s[l]);_add(x[l]);_add(y[l]);
for(auto [l, r] : dd) {
del(l, r);
}
upd(l, -a[l]);
ll delt = (r - a[l]);
if(l - 1 >= 1) tr1.upd(l - 1, l - 1, delt, 1, 1, n);
tr1.upd(l, n, -delt, 1, 1, n);
a[l] = r;
upd(l, a[l]);
// exit(0);
{
int nx = getr(l + 1, l);
while(nx <= n) {
if(get(l + 1, nx) < a[l]) {
add(l + 1, nx);
} else break;
nx = getr(l + 1, nx);
}
}
{
int prv = getl(l, l - 1);
while(prv >= 1) {
if(get(prv, l - 1) < a[l]) {
add(prv, l - 1);
} else break;
prv = getl(prv, l - 1);
}
}
{
int nx = getr(l, l - 1), prv = getl(l + 1, l);
while(nx <= n && prv >= 1) {
ll val = get(prv, nx);
if(val >= a[prv - 1]) {
prv = getl(prv, nx);
} else if(val >= a[nx + 1]) {
nx = getr(prv, nx);
} else {
add(prv, nx);
if(a[prv - 1] < a[nx + 1]) {
prv = getl(prv, nx);
} else {
nx = getr(prv, nx);
}
}
}
}
}
void test() {
cin >> n;
tr1.init();
tr2.init();
a[0] = a[n + 1] = inf;
ll pr = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 1; i <= n; i++) {
pr += a[i];
tr1.upd1(i, a[i + 1] - pr, 1, 1, n);
}
build();
prec();
assert(sum <= n * 23);
cin >> q;
while(q--) {
int tp, l, r;
cin >> tp >> l >> r;
if(tp == 2) {
int res = 0;
ll X = a[l - 1], Y = a[r + 1];
if(l - 1 >= 1) u(l - 1, inf);
if(r + 1 <= n) u(r + 1, inf);
res = get1(l, r).second;
cout << res << "\n";
if(l - 1 >= 1) u(l - 1, X);
if(r + 1 <= n) u(r + 1, Y);
} else {
u(l, r);
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--) {
test();
}
}
