//https://codeforces.com/blog/entry/101003?#comment-898608
#include <bits/stdc++.h>
using namespace std;
//loops (warning : long long)
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r - 1); i >= l; --i)
//pairs, tuples
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
//vectors
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sum_of(v) accumulate(all(v), 0ll)
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))
//binary search
#define lwb lower_bound
#define upb upper_bound
//other stuffs
#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using db = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAX = 1e5 + 5;
const ll inf = 1e15 + 100;
int N, Q;
ll a[MAX];
ll pref[MAX];
set<int> left_endpoint[MAX], right_endpoint[MAX];
struct FenwickTree{
const int offset = 0;
vl bit;
void init(int n){
bit = vl(n+1, 0);
}
void update(int i, ll v){
i += offset;
for(; i < sz(bit); i += i & (-i)) bit[i] += v;
}
ll queryPrefix(int i){
ll sum = 0;
i += offset;
for(; i > 0; i -= i & (-i)) sum += bit[i];
return sum;
}
ll query(int l, int r){
return queryPrefix(r) - queryPrefix(l-1);
}
} Fenwick;
struct SegmentTreeMinCount{
struct Node{
int mn, cnt;
Node() : mn(0), cnt(0) {}
Node(int mn, int cnt) : mn(mn), cnt(cnt) {}
friend Node operator + (const Node& a, const Node& b){
if(a.mn == b.mn) return Node(a.mn, a.cnt + b.cnt);
else return (a.mn < b.mn ? a : b);
}
};
vector<Node> st;
vi lazy;
int N;
SegmentTreeMinCount(int n) : N(n), st(n << 2), lazy(n << 2) {}
void apply(int id, int delta){
st[id].mn += delta;
lazy[id] += delta;
}
void down(int id){
if(lazy[id] != 0){
apply(id << 1, lazy[id]);
apply(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
}
void build(int id, int l, int r){
st[id].cnt = r - l + 1;
if(l < r){
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
}
void update(int id, int l, int r, int u, int v, int delta){
if(u <= l && r <= v) apply(id, delta);
else{
int mid = l + r >> 1;
down(id);
if(u <= mid) update(id << 1, l, mid, u, v, delta);
if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, delta);
st[id] = st[id << 1] + st[id << 1 | 1];
}
}
Node query(int id, int l, int r, int u, int v){
if(u <= l && r <= v) return st[id];
int mid = l + r >> 1;
down(id);
if(u > mid) return query(id << 1 | 1, mid + 1, r, u, v);
if(mid >= v) return query(id << 1, l, mid, u, v);
return query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v);
}
int count_min(int l, int r){
Node cur = query(1, 1, N, l, r);
return cur.cnt;
}
} MinCount(0);
struct SegmentTreeRightEndpoint{
vl st, lazy;
void init(int n){
st.resize(4 * n, 0);
lazy.resize(4 * n, 0);
}
void apply(int id, ll val){
st[id] += val;
lazy[id] += val;
}
void down(int id){
if(lazy[id] != 0){
apply(id << 1, lazy[id]);
apply(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
}
void build(int id, int l, int r){
if(l == r){
//pref[j-1] - pref[i] < a[j]
//<=> pref[j-1] - a[j] < pref[i]
st[id] = pref[l-1] - a[l];
} else{
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
}
void update(int id, int l, int r, int u, int v, ll delta){
if(u <= l && r <= v) apply(id, delta);
else{
int mid = l + r >> 1;
down(id);
if(u <= mid) update(id << 1, l, mid, u, v, delta);
if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, delta);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
}
int find_next(int id, int l, int r, int u, int v, ll s){
if(v < l || u > r) return -1;
if(st[id] >= s) return -1;
if(u <= l && r <= v){
while(l < r){
int mid = l + r >> 1;
down(id);
if(st[id << 1] < s) id = id << 1, r = mid;
else id = id << 1 | 1, l = mid + 1;
}
return l;
} else{
int mid = l + r >> 1;
down(id);
int go = find_next(id << 1, l, mid, u, v, s);
if(go != -1) return go;
return find_next(id << 1 | 1, mid + 1, r, u, v, s);
}
}
int find_next(int l, int r, ll s){
if(l > r) return N+1;
int R = find_next(1, 1, N, l, r, s);
if(R == -1) return N+1;
return R;
}
} TreeRightEndpoint;
struct SegmentTreeLeftEndpoint{
vl st, lazy;
void init(int n){
st.resize(4 * n, 0);
lazy.resize(4 * n, 0);
}
void apply(int id, ll val){
st[id] += val;
lazy[id] += val;
}
void down(int id){
if(lazy[id] != 0){
apply(id << 1, lazy[id]);
apply(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
}
void build(int id, int l, int r){
if(l == r){
//pref[j-1] - pref[i] < a[i]
//pref[j] < pref[i] + a[i]
st[id] = pref[l] + a[l];
} else{
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
}
void update(int id, int l, int r, int u, int v, ll delta){
if(u <= l && r <= v) apply(id, delta);
else{
int mid = l + r >> 1;
down(id);
if(u <= mid) update(id << 1, l, mid, u, v, delta);
if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, delta);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
}
int find_next(int id, int l, int r, int u, int v, ll s){
if(v < l || u > r) return -1;
if(st[id] <= s) return -1;
if(u <= l && r <= v){
while(l < r){
int mid = l + r >> 1;
down(id);
if(st[id << 1 | 1] > s) id = id << 1 | 1, l = mid + 1;
else id = id << 1, r = mid;
}
return l;
} else{
int mid = l + r >> 1;
down(id);
int go = find_next(id << 1 | 1, mid + 1, r, u, v, s);
if(go != -1) return go;
return find_next(id << 1, l, mid, u, v, s);
}
}
int find_next(int l, int r, ll s){
if(l > r) return 0;
int L = find_next(1, 1, N, l, r, s);
if(L == -1) L = 0;
return L;
}
} TreeLeftEndpoint;
void add_segment(int l, int r){
assert(r-l > 1);
MinCount.update(1, 1, N, l+1, r-1, +1);
left_endpoint[l].insert(r);
right_endpoint[r].insert(l);
}
void erase_segment(int l, int r){
assert(r-l > 1);
MinCount.update(1, 1, N, l+1, r-1, -1);
left_endpoint[l].erase(r);
right_endpoint[r].erase(l);
}
bool bad(int l, int r){
assert(r-l > 1);
return min(a[l], a[r]) > Fenwick.query(l+1, r-1);
}
void update(int i, int x){
vpi segments;
int l = i-1, r = i+1;
while(true){
if(bad(l, r)) segments.eb(l, r);
if(l == 0 && r == N+1) break;
if(a[l] < a[r]) l = TreeLeftEndpoint.find_next(1, l-1, Fenwick.queryPrefix(r-1)); //can't extend right
else r = TreeRightEndpoint.find_next(r+1, N, Fenwick.queryPrefix(l)); //can't extend left
}
for(auto r : left_endpoint[i-1]) segments.eb(i-1, r);
for(auto l : right_endpoint[i+1]) segments.eb(l, i+1);
sort(all(segments)); compact(segments);
for(auto [l, r] : segments) erase_segment(l, r);
segments.clear();
Fenwick.update(i, -a[i] + x);
TreeLeftEndpoint.update(1, 1, N, i, N, -a[i] + x);
TreeLeftEndpoint.update(1, 1, N, i, i, -a[i] + x);
if(i < N) TreeRightEndpoint.update(1, 1, N, i+1, N, -a[i] + x);
TreeRightEndpoint.update(1, 1, N, i, i, +a[i] - x);
a[i] = x;
l = i-1, r = i+1;
while(true){
if(bad(l, r)) {
segments.eb(l, r);
}
if(l == 0 && r == N+1) break;
if(a[l] < a[r]) l = TreeLeftEndpoint.find_next(1, l-1, Fenwick.queryPrefix(r-1)); //can't extend right
else r = TreeRightEndpoint.find_next(r+1, N, Fenwick.queryPrefix(l)); //can't extend left
}
r = i+1;
while(true){
if(bad(i-1, r)) segments.eb(i-1, r);
if(r == N+1) break;
r = TreeRightEndpoint.find_next(r+1, N, Fenwick.queryPrefix(i-1));
}
l = i-1;
while(true){
if(bad(l, i+1)) segments.eb(l, i+1);
if(l == 0) break;
l = TreeLeftEndpoint.find_next(1, l-1, Fenwick.queryPrefix(i));
}
sort(all(segments)); compact(segments);
for(auto [l, r] : segments) add_segment(l, r);
}
ll query(int l, int r){
int R = r;
while(true){
int nxt = TreeLeftEndpoint.find_next(1, R-1, Fenwick.queryPrefix(r));
if(nxt < l) break;
R = nxt;
}
int L = l;
while(true){
int nxt = TreeRightEndpoint.find_next(L+1, N, Fenwick.queryPrefix(l-1));
if(nxt > r) break;
L = nxt;
}
int result = MinCount.count_min(L, R);
return result;
}
void testcase(int ntestcase){
cin >> N;
a[0] = a[N+1] = inf;
FOR(i, 1, N+1) {
cin >> a[i];
pref[i] = pref[i-1] + a[i];
}
Fenwick.init(N);
TreeLeftEndpoint.init(N);
TreeRightEndpoint.init(N);
MinCount = SegmentTreeMinCount(N);
FOR(i, 1, N+1) Fenwick.update(i, +a[i]);
TreeLeftEndpoint.build(1, 1, N);
TreeRightEndpoint.build(1, 1, N);
MinCount.build(1, 1, N);
FOR(i, 0, N){
//finding all j that min(a[i], a[j]) > sum[i+1, j-1]
//<=> pref[j-1] - pref[i] < min(a[i], a[j])
int j = i+2;
while(true){
if(pref[j-1] - pref[i] < min(a[i], a[j])) add_segment(i, j);
if(j > N) break;
j = TreeRightEndpoint.find_next(j+1, N, pref[i]);
}
}
cin >> Q;
while(Q--){
int t;
cin >> t;
if(t == 1){
int x, y;
cin >> x >> y;
update(x, y);
} else{
int l, r;
cin >> l >> r;
cout << query(l, r) << '\n';
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("main.out", "w", stdout);
#endif // LOCAL
int T = 1;
// cin >> T;
FOR(i, 0, T) testcase(i);
return 0;
}
