#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, q;
ll a[maxn], pref[maxn];
void input()
{
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i];
cin >> q;
a[0] = 1e9 + 10;
a[n + 1] = 1e9 + 10;
}
struct interval
{
int left, right, pivot;
interval(int _left = 0, int _right = 0, int _pivot = 0)
{
left = _left;
right = _right;
pivot = _pivot;
}
bool operator < (const interval &it) const
{
if (left != it.left)
return left < it.left;
if (right != it.right)
return right > it.right;
///assert(pivot != it.pivot);
return pivot < it.pivot;
}
};
set < interval > ranges;
void get_ranges()
{
for (int i = 1; i <= n; i ++)
pref[i] = pref[i - 1] + a[i];
pref[n + 1] = pref[n];
ranges.clear();
stack < int > st;
st.push(0);
for (int i = 1; i <= n; i ++)
{
while(!st.empty() && a[st.top()] < a[i])
st.pop();
ranges.insert(interval(st.top(), i, i));
st.push(i);
}
while(!st.empty())
st.pop();
st.push(n + 1);
for (int i = n; i > 0; i --)
{
while(!st.empty() && a[st.top()] < a[i])
st.pop();
ranges.insert(interval(i, st.top(), i));
st.push(i);
}
}
int b[maxn];
struct node
{
int cnt, mx;
node(int _cnt = 0, int _mx = 1e9 + 10)
{
cnt = _cnt;
mx = _mx;
}
};
node tree[4 * maxn];
node merge_node(node lf, node rf)
{
if (lf.cnt == -1 || rf.mx < lf.mx)
return rf;
if (rf.cnt == -1 || lf.mx < rf.mx)
return lf;
return node(lf.cnt + rf.cnt, lf.mx);
}
void build_tree(int root, int left, int right)
{
if (left == right)
{
tree[root].mx = b[left];
tree[root].cnt = 1;
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
node query(int root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft)
return node(-1, 1e9 + 10);
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return merge_node(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
ll values[maxn];
struct segment_tree
{
ll tree[4 * maxn], lazy[4 * maxn];
void build_tree(int root, int left, int right)
{
lazy[root] = 0;
if (left == right)
{
tree[root] = values[left];
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}
void push_lazy(int root, int left, int right)
{
tree[root] += lazy[root];
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
}
lazy[root] = 0;
}
void update_range(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] += val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
update_range(root * 2, left, mid, qleft, qright, val);
update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}
ll walk_left(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft || tree[root] <= val)
return n + 1;
if (left == right)
return left;
int mid = (left + right) / 2;
if (left >= qleft && right <= qright)
{
push_lazy(root * 2, left, mid);
push_lazy(root * 2 + 1, mid + 1, right);
if (tree[root * 2] > val)
return walk_left(root * 2, left, mid, qleft, qright, val);
return walk_left(root * 2 + 1, mid + 1, right, qleft, qright, val);
}
return min(walk_left(root * 2, left, mid, qleft, qright, val),
walk_left(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
ll walk_right(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft || tree[root] <= val)
return 0;
if (left == right)
return left;
int mid = (left + right) / 2;
if (left >= qleft && right <= qright)
{
push_lazy(root * 2, left, mid);
push_lazy(root * 2 + 1, mid + 1, right);
if (tree[root * 2 + 1] > val)
return walk_right(root * 2 + 1, mid + 1, right, qleft, qright, val);
return walk_right(root * 2, left, mid, qleft, qright, val);
}
return max(walk_right(root * 2, left, mid, qleft, qright, val),
walk_right(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
};
segment_tree left_tree, right_tree;
ll fen[maxn];
void update_fen(int pos, ll val)
{
for (int i = pos; i <= n; i += (i & -i))
fen[i] += val;
}
ll query_fen(int pos)
{
ll s = 0;
for (int i = pos; i > 0; i -= (i & -i))
s += fen[i];
return s;
}
ll range_sum(int left, int right)
{
return query_fen(right) - query_fen(left - 1);
}
void solve_query(int left, int right)
{
int lb = left_tree.walk_right(1, 1, n, left, right, - query_fen(left - 1));
int rb = right_tree.walk_left(1, 1, n, left, right, query_fen(right));
cout << query(1, 1, n, lb, rb).cnt << endl;
}
void restructure()
{
///cout << "-------------" << endl;
get_ranges();
for (int i = 1; i <= n; i ++)
b[i] = 0;
for (interval cur : ranges)
{
ll mx = min(a[cur.left], a[cur.right]);
if (range_sum(cur.left + 1, cur.right - 1) < mx)
{
///cout << cur.left << " " << cur.right << endl;
for (int i = cur.left + 1; i < cur.right; i ++)
b[i] ++;
}
}
build_tree(1, 1, n);
}
void simulate()
{
for (int i = 1; i <= n; i ++)
update_fen(i, a[i]);
restructure();
for (int i = 1; i <= n; i ++)
{
values[i] = a[i] - query_fen(i - 1);
}
left_tree.build_tree(1, 1, n);
for (int i = 1; i <= n; i ++)
{
values[i] = a[i] + query_fen(i);
}
right_tree.build_tree(1, 1, n);
for (int i = 1; i <= q; i ++)
{
int type;
cin >> type;
if (type == 1)
{
int idx;
ll x;
cin >> idx >> x;
update_fen(idx, x - a[idx]);
left_tree.update_range(1, 1, n, idx + 1, n, - (x - a[idx]));
left_tree.update_range(1, 1, n, idx, idx, (x - a[idx]));
right_tree.update_range(1, 1, n, idx, n, (x - a[idx]));
right_tree.update_range(1, 1, n, idx, idx, (x - a[idx]));
a[idx] = x;
restructure();
}
else
{
int l, r;
cin >> l >> r;
solve_query(l, r);
}
}
}
void solve()
{
input();
simulate();
}
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int main()
{
speed();
solve();
return 0;
}
/*
12
32 32 4 1 1 1 1 4 4 16 32 128
1
2 8 10
*/
