// ~ Be Name Khoda ~
#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops,O3")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 2e7 + 10;
const int maxn5 = 1e5 + 10;
const int maxnt = 5e5 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
int a[maxn5];
int n;
vector <int> av;
namespace fen{
ll fen[maxn5];
inline void add(int id, ll val){
for(++id; id < maxn5; id += id & -id)
fen[id] += val;
}
inline ll get(int id){
ll ret = 0;
for(++id; id; id -= id & -id)
ret += fen[id];
return ret;
}
inline ll get(int l, int r){
if(r < l || r < 0)
return 0;
if(l == r)
return a[l];
return get(r) - (l ? get(l - 1) : 0);
}
}
namespace seg{
pii mn[maxnt];
int lazy[maxnt], mx[maxnt];
inline pii comb(pii a, pii b){
pii ans = min(a, b);
if(a.fi == b.fi)
ans.se = a.se + b.se;
return ans;
}
void build(int l, int r, int v){
mn[v] = {0, r - l};
if(r - l == 1)
return;
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
}
void upd(int l, int r, int id, int v){
if(r - l == 1){
mx[v] = a[id];
return;
}
int mid = (l + r) >> 1;
if(id < mid)
upd(l, mid, id, v * 2);
else
upd(mid, r, id, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}
void add(int l, int r, int lq, int rq, int val, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
lazy[v] += val;
mn[v].fi += val;
return;
}
int mid = (l + r) >> 1;
add(l, mid, lq, rq, val, v * 2);
add(mid, r, lq, rq, val, v * 2 + 1);
mn[v] = comb(mn[v * 2], mn[v * 2 + 1]);
mn[v].fi += lazy[v];
}
pii get_min(int l, int r, int lq, int rq, int v){
if(rq <= l || r <= lq)
return {mod, 0};
if(lq <= l && r <= rq)
return mn[v];
int mid = (l + r) >> 1;
pii ans = comb(get_min(l, mid, lq, rq, v * 2), get_min(mid, r, lq, rq, v * 2 + 1));
ans.fi += lazy[v];
return ans;
}
int get_first(int l, int r, int lq, int rq, ll val, int v){
if(rq <= l || r <= lq || mx[v] < val)
return -1;
if(r - l == 1)
return l;
int mid = (l + r) >> 1;
int ans = get_first(l, mid, lq, rq, val, v * 2);
if(ans != -1)
return ans;
return get_first(mid, r, lq, rq, val, v * 2 + 1);
}
int get_last(int l, int r, int lq, int rq, ll val, int v){
if(rq <= l || r <= lq || mx[v] < val)
return -1;
if(r - l == 1)
return l;
int mid = (l + r) >> 1;
int ans = get_last(mid, r, lq, rq, val, v * 2 + 1);
if(ans != -1)
return ans;
return get_last(l, mid, lq, rq, val, v * 2);
}
}
struct segment_tree{
ll lazy[maxnt], mx[maxnt];
void add(int l, int r, int lq, int rq, ll val, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
lazy[v] += val;
mx[v] += val;
return;
}
int mid = (l + r) >> 1;
add(l, mid, lq, rq, val, v * 2);
add(mid, r, lq, rq, val, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]) + lazy[v];
}
int get_first(int l, int r, int lq, int rq, ll val, int v){
if(rq <= l || r <= lq || mx[v] < val)
return -1;
if(r - l == 1)
return l;
int mid = (l + r) >> 1;
val -= lazy[v];
int ans = get_first(l, mid, lq, rq, val, v * 2);
if(ans != -1)
return ans;
return get_first(mid, r, lq, rq, val, v * 2 + 1);
}
int get_last(int l, int r, int lq, int rq, ll val, int v){
if(rq <= l || r <= lq || mx[v] < val)
return -1;
if(r - l == 1)
return l;
int mid = (l + r) >> 1;
val -= lazy[v];
int ans = get_last(mid, r, lq, rq, val, v * 2 + 1);
if(ans != -1)
return ans;
return get_last(l, mid, lq, rq, val, v * 2);
}
} segpre, segsuf;
inline void chval(int id, int val){
fen::add(id, val - a[id]);
segpre.add(0, n, id + 1, n, a[id] - val, 1);
segpre.add(0, n, id, id + 1, val - a[id], 1);
segsuf.add(0, n, 0, id, a[id] - val, 1);
segsuf.add(0, n, id, id + 1, val - a[id], 1);
a[id] = val;
seg::upd(0, n, id, 1);
}
inline void update(int x, int y){
//cerr << "ya here " << x << ' ' << y << '\n';
if(y == a[x])
return;
if(y > a[x]){
ll sum1 = a[x], sum2 = a[x];
int i1 = seg::get_last(0, n, 0, x, a[x] + 1, 1);
int i2 = seg::get_first(0, n, x + 1, n, a[x] + 1, 1);
while(i1 != -1 && i2 != -1){
ll sum = fen::get(i1 + 1, i2 - 1);
if(sum < min(a[i1], a[i2]) && sum - a[x] + y >= min(a[i1], a[i2]))
seg::add(0, n, i1 + 1, i2, -1, 1);
if(a[i1] <= a[i2]){
sum1 += a[i1];
i1 = seg::get_last(0, n, 0, i1, sum1 + 1, 1);
}
else{
sum2 += a[i2];
i2 = seg::get_first(0, n, i2, n, sum2 + 1, 1);
}
}
ll sum = 0;
int i = seg::get_first(0, n, x + 1, n, a[x], 1);
while(i != -1){
ll have = fen::get(x + 1, i - 1);
if(have >= min(a[x], a[i]) && have < min(y, a[i]))
seg::add(0, n, x + 1, i, 1, 1);
sum += a[i];
i = seg::get_first(0, n, i + 1, n, sum + 1, 1);
}
sum = 0;
i = seg::get_last(0, n, 0, x, a[x], 1);
while(i != -1){
ll have = fen::get(i + 1, x - 1);
if(have >= min(a[x], a[i]) && have < min(y, a[i]))
seg::add(0, n, i + 1, x, 1, 1);
sum += a[i];
i = seg::get_last(0, n, 0, i, sum + 1, 1);
}
chval(x, y);
return;
}
ll sum1 = y, sum2 = y;
int i1 = seg::get_last(0, n, 0, x, y + 1, 1);
int i2 = seg::get_first(0, n, x + 1, n, y + 1, 1);
while(i1 != -1 && i2 != -1){
ll sum = fen::get(i1 + 1, i2 - 1);
if(sum >= min(a[i1], a[i2]) && sum - a[x] + y < min(a[i1], a[i2]))
seg::add(0, n, i1 + 1, i2, 1, 1);
if(a[i1] <= a[i2]){
sum1 += a[i1];
i1 = seg::get_last(0, n, 0, i1, sum1 + 1, 1);
}
else{
sum2 += a[i2];
i2 = seg::get_first(0, n, i2, n, sum2 + 1, 1);
}
}
ll sum = 0;
int i = x + 1;
while(i != -1){
ll have = fen::get(x + 1, i - 1);
if(have < min(a[x], a[i]) && have >= min(y, a[i]))
seg::add(0, n, x + 1, i, -1, 1);
sum += a[i];
i = seg::get_first(0, n, i + 1, n, sum + 1, 1);
}
sum = 0;
i = x - 1;
while(i != -1){
ll have = fen::get(i + 1, x - 1);
if(have < min(a[x], a[i]) && have >= min(y, a[i]))
seg::add(0, n, i + 1, x, -1, 1);
sum += a[i];
i = seg::get_last(0, n, 0, i, sum + 1, 1);
}
chval(x, y);
return;
}
inline void add(int l, int r){
ll sum = fen::get(l + 1, r - 1);
if(sum >= min(a[l], a[r]))
return;
seg::add(0, n, l + 1, r, 1, 1);
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
seg::build(0, n, 1);
for(int i = 0; i < n; i++){
int keep;
cin >> keep;
chval(i, keep);
while(av.size() && a[av.back()] <= a[i]){
add(av.back(), i);
av.pop_back();
}
if(av.size())
add(av.back(), i);
av.pb(i);
}
int q; cin >> q;
while(q--){
int ty, x, y; cin >> ty >> x >> y;
x--;
if(ty == 1)
update(x, y);
else{
y--;
ll sumpre = fen::get(0, x - 1);
int l = segpre.get_last(0, n, x, y + 1, (-sumpre) + 1, 1);
if(l == -1)
l = x;
sumpre = fen::get(y + 1, n);
int r = segsuf.get_first(0, n, x, y + 1, (-sumpre) + 1, 1);
if(r == -1)
r = y;
cout << seg::get_min(0, n, l, r + 1, 1).se << '\n';
}
}
}
/*
5
6 4 2 2 6
3
1 3 1
2 2 5
2 1 5
2 2 4
5
6 4 2 2 6
1
2 1 3
2 1 5
1 3 1
2 2 5
2 1 5
2 2 4
3
6 4 2
1
2 1 2
10
2 3 5 10 1 3 4 9 5 2
2
1 4 1000000000
2 1 10
1 8 20
1 4 8
2 1 10
7
27 18 36 31 55 86 4
4
1 7 18
1 7 60
1 3 11
2 1 6
7
27 18 36 31 55 86 60
3
2 2 3
1 3 11
2 1 6
8
41 53 10 12 43 91 11 92
10
2 5 8
1 8 65
2 4 7
2 3 8
1 2 37
1 8 5
2 7 8
1 8 43
1 1 30
1 6 60
*/
