#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 inf64 = 1ll << 50;
constexpr int inf = 1000000000;
template <class M>
class segTree {
int n, size;
using T = typename M::T;
std::vector<T> data;
void update(int i) {
data[i] = M::op(data[2 * i], data[2 * i + 1]);
}
public:
segTree(int n_) : n(n_) {
size = 1;
while (size < n) {
size *= 2;
}
data.assign(2 * size, M::id());
}
void set(int i, T v) {
i += size;
data[i] = v;
while (i != 1) {
i /= 2;
update(i);
}
}
T fold(int l, int r) {
T pl = M::id(), pr = M::id();
for (l += size, r += size; l < r; l /= 2, r /= 2) {
if (l % 2 == 1) {
pl = M::op(pl, data[l++]);
}
if (r % 2 == 1) {
pr = M::op(data[--r], pr);
}
}
return M::op(pl, pr);
}
template <class F>
int maxRight(int l, F f) {
assert(f(M::id()));
if (l == n) {
return n;
}
l += size;
T p = M::id();
do {
while (l % 2 == 0) {
l /= 2;
}
if (not f(M::op(p, data[l]))) {
while (l < size) {
l *= 2;
if (f(M::op(p, data[l]))) {
p = M::op(p, data[l]);
++l;
}
}
return l - size;
}
p = M::op(p, data[l]);
++l;
} while ((l & (-l)) != l);
return n;
}
template <class F>
int minLeft(int r, F f) {
assert(f(M::id()));
if (r == 0) {
return 0;
}
r += size;
T p = M::id();
do {
--r;
while (r > 1 and (r % 2 == 1)) {
r /= 2;
}
if (not f(M::op(data[r], p))) {
while (r < size) {
r = 2 * r + 1;
if (f(M::op(data[r], p))) {
p = M::op(data[r], p);
--r;
}
}
return r + 1 - size;
}
} while ((r & (-r)) != r);
return 0;
}
};
constexpr int B = 1000;
struct rangeSum64 {
using T = i64;
static T op(T a, T b) {
return a + b;
}
static T id() {
return 0;
}
};
struct rangeMax64 {
using T = i64;
static T op(T a, T b) {
return std::max(a, b);
}
static T id() {
return -inf64;
}
};
struct rangeMaxWithIndex32 {
using T = std::pair<int, int>;
static T op(T a, T b) {
return std::max(a, b);
}
static T id() {
return {-inf, 0};
}
};
struct rangeSum32 {
using T = int;
static T op(T a, T b) {
return a + b;
}
static T id() {
return 0;
}
};
struct rangeMax32 {
using T = int;
static T op(T a, T b) {
return std::max(a, b);
}
static T id() {
return -inf;
}
};
int main() {
// input
int N;
std::cin >> N;
std::vector<i64> A(N);
for (auto &e : A) {
std::cin >> e;
}
segTree<rangeSum64> sumA(N);
segTree<rangeMax64> maxA(N);
for (int i = 0; i < N; ++i) {
sumA.set(i, A[i]);
maxA.set(i, A[i]);
}
segTree<rangeMaxWithIndex32> maxR(N);
auto expandRange = [&](int &l, int &r) {
while (true) {
const auto sum = sumA.fold(l, r);
const auto limitL = maxA.minLeft(l, [&](const auto v) { return v <= sum; });
const auto limitR = maxA.maxRight(r, [&](const auto v) { return v <= sum; });
const auto newL = limitL, newR = limitR;
if (l == newL and r == newR) {
break;
}
l = newL;
r = newR;
}
};
auto findRanges = [&](const int m, auto f) {
int l = m, r = m + 1;
while (true) {
expandRange(l, r);
if (l == 0 and r == N) {
break;
}
f(l, r);
if (l == 0) {
++r;
continue;
}
if (r == N) {
--l;
continue;
}
if (A[l - 1] < A[r]) {
--l;
} else {
++r;
}
}
};
auto eraseRanges = [&](const int m, auto f) {
while (true) {
const auto [ma, i] = maxR.fold(0, m + 1);
if (ma <= m) {
break;
}
f(i, ma);
}
};
std::vector<std::set<int>> rangesEachL(N);
std::vector<int> countShortRanges(N);
segTree<rangeSum32> sumPoints(N);
segTree<rangeMax32> maxLargeRangesR(N);
for (int i = 0; i < N; ++i) {
sumPoints.set(i, 1);
}
auto addPoint = [&](const int i, const int d) {
assert(d == 1 or d == -1);
if (countShortRanges[i] == 0 and d == 1) {
sumPoints.set(i, 0);
}
if (countShortRanges[i] == 1 and d == -1) {
sumPoints.set(i, 1);
}
countShortRanges[i] += d;
assert(0 <= countShortRanges[i]);
};
auto applyAddRange = [&](int l, int r) {
if (rangesEachL[l].find(r) != rangesEachL[l].end()) {
return;
}
rangesEachL[l].insert(r);
maxR.set(l, {rangesEachL[l].empty() ? -inf : *rangesEachL[l].rbegin(), l});
if (r - l < B) {
for (int i = l; i < r; ++i) {
addPoint(i, 1);
}
} else {
maxLargeRangesR.set(l, *rangesEachL[l].rbegin());
}
};
auto applyEraseRange = [&](int l, int r) {
assert(rangesEachL[l].find(r) != rangesEachL[l].end());
rangesEachL[l].erase(r);
maxR.set(l, {rangesEachL[l].empty() ? -inf : *rangesEachL[l].rbegin(), l});
if (r - l < B) {
for (int i = l; i < r; ++i) {
addPoint(i, -1);
}
} else {
if (not rangesEachL[l].empty()) {
const auto v = *rangesEachL[l].rbegin();
if (v - l >= B) {
maxLargeRangesR.set(l, v);
} else {
maxLargeRangesR.set(l, -inf);
}
} else {
maxLargeRangesR.set(l, -inf);
}
}
};
for (int i = 0; i < N; ++i) {
findRanges(i, applyAddRange);
}
// answer queries
int Q;
std::cin >> Q;
while (Q--) {
int t;
std::cin >> t;
if (t == 1) {
int x;
i64 y;
std::cin >> x >> y;
--x;
A[x] = y;
sumA.set(x, y);
maxA.set(x, y);
eraseRanges(x, applyEraseRange);
if (x != 0) {
eraseRanges(x - 1, applyEraseRange);
}
if (x != N - 1) {
eraseRanges(x + 1, applyEraseRange);
}
findRanges(x, applyAddRange);
if (x != 0) {
findRanges(x - 1, applyAddRange);
}
if (x != N - 1) {
findRanges(x + 1, applyAddRange);
}
}
if (t == 2) {
int l, r;
std::cin >> l >> r;
--l;
// find true l and r
i64 memo = -1;
int realL = l;
if (l != 0) {
memo = A[l - 1];
A[l - 1] = inf64;
sumA.set(l - 1, A[l - 1]);
maxA.set(l - 1, A[l - 1]);
}
findRanges(l, [&](int a, int b) {
assert(a == l);
if (b < r) {
realL = b;
}
});
if (l != 0) {
A[l - 1] = memo;
sumA.set(l - 1, A[l - 1]);
maxA.set(l - 1, A[l - 1]);
}
int realR = r;
if (r != N) {
memo = A[r];
A[r] = inf64;
sumA.set(r, A[r]);
maxA.set(r, A[r]);
}
findRanges(r - 1, [&](int a, int b) {
assert(b == r);
if (a > l) {
realR = a;
}
});
if (r != N) {
A[r] = memo;
sumA.set(r, A[r]);
maxA.set(r, A[r]);
}
assert(realL < realR);
if (r - l < B) {
std::vector<int> imos(r - l + 1);
auto itr = rangesEachL[l].lower_bound(r);
if (itr != rangesEachL[l].begin()) {
--itr;
++imos[0];
--imos[*itr - l];
}
for (int i = l + 1; i < r; ++i) {
if (rangesEachL[i].empty()) {
continue;
}
auto avalR = rangesEachL[i].rbegin();
++imos[i - l];
--imos[std::min(r, *avalR) - l];
}
int answer = 0;
for (int i = 0; i < r - l; ++i) {
if (realL <= i + l and i + l < realR and imos[i] == 0) {
++answer;
}
imos[i + 1] += imos[i];
}
std::cout << answer << std::endl;
continue;
}
int answer = 0;
auto itr = rangesEachL[l].lower_bound(r);
int nowR = realL;
if (realL == l) {
if (countShortRanges[l] == 0) {
++answer;
}
++nowR;
}
while (nowR < realR) {
const auto nextR = maxLargeRangesR.fold(l + 1, nowR + 1);
if (nextR > nowR) {
nowR = nextR;
} else {
// problem...
const auto nextStep = maxLargeRangesR.maxRight(nowR, [&](const auto v) {
return v <= nowR;
});
answer += sumPoints.fold(nowR, std::min(realR, nextStep));
nowR = nextStep;
}
}
std::cout << answer << std::endl;
}
}
}
