// https://oj.uz/submission/937840
// https://codeforces.com/blog/entry/101003?#comment-898608
// https://www2.ioi-jp.org/camp/2022/2022-sp-tasks/contest4/fish2-review.pdf
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 1e5 + 5, inf = 1e9 + 7;
int n, q;
int a[N], ma[4 * N], lz[4 * N];
array<int, 2> s[4 * N];
array<int, 2> operator + (const array<int, 2> <, const array<int, 2> &rt) {
array<int, 2> res{};
res[0] = min(lt[0], rt[0]);
if (res[0] == lt[0]) {
res[1] += lt[1];
}
if (res[0] == rt[0]) {
res[1] += rt[1];
}
return res;
}
namespace ft {
long long ft[N];
void upd(int i, int x) {
for (; i <= n; i += i & -i) {
ft[i] += x;
}
}
long long qry(int i) {
long long res = 0;
for (; i; i -= i & -i) {
res += ft[i];
}
return res;
}
long long qry(int l, int r) {
return qry(r) - qry(l - 1);
}
}
void upd(int i, int x, int id = 1, int l = 1, int r = n) {
if (l == r) {
ma[id] = x;
return;
}
int md = (l + r) / 2;
if (i <= md) {
upd(i, x, id * 2, l, md);
} else {
upd(i, x, id * 2 + 1, md + 1, r);
}
ma[id] = max(ma[id * 2], ma[id * 2 + 1]);
}
int walklt(int i, long long k, int id = 1, int l = 1, int r = n) {
if (l >= i || ma[id] <= k) {
return 0;
}
if (l == r) {
return l;
}
int md = (l + r) / 2;
auto res = walklt(i, k, id * 2 + 1, md + 1, r);
return res == 0 ? walklt(i, k, id * 2, l, md) : res;
}
int walkrt(int i, long long k, int id = 1, int l = 1, int r = n) {
if (r <= i || ma[id] <= k) {
return n + 1;
}
if (l == r) {
return l;
}
int md = (l + r) / 2;
auto res = walkrt(i, k, id * 2, l, md);
return res == n + 1 ? walkrt(i, k, id * 2 + 1, md + 1, r) : res;
}
void app(int id, int x) {
s[id][0] += x;
lz[id] += x;
}
void psh(int id) {
if (lz[id]) {
app(id * 2, lz[id]);
app(id * 2 + 1, lz[id]);
lz[id] = 0;
}
}
void bld(int id = 1, int l = 1, int r = n) {
if (l == r) {
s[id] = {0, 1};
return;
}
int md = (l + r) / 2;
bld(id * 2, l, md);
bld(id * 2 + 1, md + 1, r);
s[id] = s[id * 2] + s[id * 2 + 1];
}
void add(int u, int v, int x, int id = 1, int l = 1, int r = n) {
if (u <= l && r <= v) {
app(id, x);
return;
}
psh(id);
int md = (l + r) / 2;
if (u <= md) {
add(u, v, x, id * 2, l, md);
}
if (md < v) {
add(u, v, x, id * 2 + 1, md + 1, r);
}
s[id] = s[id * 2] + s[id * 2 + 1];
}
array<int, 2> get(int u, int v, int id = 1, int l = 1, int r = n) {
if (u <= l && r <= v) {
return s[id];
}
psh(id);
int md = (l + r) / 2;
if (v <= md) {
return get(u, v, id * 2, l, md);
}
if (md < u) {
return get(u, v, id * 2 + 1, md + 1, r);
}
return get(u, v, id * 2, l, md) + get(u, v, id * 2 + 1, md + 1, r);
}
bool check(int l, int r, long long &sum) {
sum = ft::qry(l + 1, r - 1);
return sum < min(a[l], a[r]);
}
vector<array<int, 2>> getcands(int p) {
if (p == 0 || p == n + 1) {
return {};
}
int l = p, r = p;
long long cur = a[p];
vector<array<int, 2>> cands;
while (1) {
int s = walklt(l, cur), e = walkrt(r, cur);
if (s == 0 && e == n + 1) {
break;
}
if (check(s, e, cur)) {
cands.push_back({s + 1, e - 1});
}
if (a[s] <= a[e]) {
l = s;
} else {
r = e;
}
}
return cands;
}
void up(int i, int x) {
auto cands = getcands(i);
auto lt = getcands(i - 1);
auto rt = getcands(i + 1);
for (auto [l, r] : cands) {
add(l, r, x);
}
for (auto [l, r] : lt) {
if (r == i - 1) {
add(l, r, x);
}
}
for (auto [l, r] : rt) {
if (l == i + 1) {
add(l, r, x);
}
}
}
void chg(int i, int x) {
up(i, -1);
ft::upd(i, x - a[i]);
a[i] = x;
upd(i, x);
up(i, 1);
}
int findlt(int l, int r) {
int res = l, p = l;
long long cur = a[l];
while (1) {
p = walkrt(p, cur);
if (p > r) {
break;
}
cur = ft::qry(l, p - 1);
if (cur < a[p]) {
res = p;
}
}
return res;
}
int findrt(int l, int r) {
int res = r, p = r;
long long cur = a[r];
while (1) {
p = walklt(p, cur);
if (p < l) {
break;
}
cur = ft::qry(p + 1, r);
if (cur < a[p]) {
res = p;
}
}
return res;
}
int qry(int l, int r) {
int s = findlt(l, r), e = findrt(l, r);
if (s > e) {
return 0;
}
return get(s, e)[1];
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
bld();
a[0] = a[n + 1] = inf;
for (int i = 1; i <= n; ++i) {
int x; cin >> x;
chg(i, x);
}
cin >> q;
while (q--) {
int t; cin >> t;
if (t == 1) {
int x, y; cin >> x >> y;
chg(x, y);
} else {
int s, e; cin >> s >> e;
cout << qry(s, e) << "\n";
}
}
return 0;
}
// an interesting observation that I haven't taken advantage of
// A >= sum(x - 1) - sum(l - 1)
// -> A - sum(x - 1) >= -sum(l - 1) (can be solved with lazy segtree)
