#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;
vector < interval > act[4 * maxn];
void add_range(int root, int left, int right, int qleft, int qright, interval cur)
{
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
//cout << "ROOT " << root << endl;
act[root].push_back(cur);
return;
}
int mid = (left + right) / 2;
add_range(root * 2, left, mid, qleft, qright, cur);
add_range(root * 2 + 1, mid + 1, right, qleft, qright, cur);
}
void rem_range(int root, int left, int right, int qleft, int qright, interval cur)
{
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
/**if (act[root].back().left != cur.left || act[root].back().right != cur.right ||
act[root].back().pivot != cur.pivot)
{
cout << "Alert!!!" << endl;
cout << act[root].back().left << " : " << act[root].back().right << " : " << act[root].back().pivot << endl;
exit(0);
}*/
//if (act[root].size() == 0)
// cout << "FUCK " << root << endl;
assert(act[root].size() > 0);
act[root].pop_back();
return;
}
int mid = (left + right) / 2;
rem_range(root * 2, left, mid, qleft, qright, cur);
rem_range(root * 2 + 1, mid + 1, right, qleft, qright, cur);
}
bool cmp_interval(const interval &it1, const interval &it2)
{
if ((it1.right - it1.left) != (it2.right - it2.left))
return (it1.right - it1.left) < (it2.right - it2.left);
if (it1.left != it2.left)
return it1.left < it2.left;
if (it1.pivot == it2.pivot)
while(true);
return (it1.pivot < it2.pivot);
}
void get_ranges()
{
ranges.clear();
stack < int > st;
st.push(0);
vector < interval > vec;
for (int i = 1; i <= n; i ++)
{
while(!st.empty() && a[st.top()] < a[i])
st.pop();
ranges.insert(interval(st.top(), i, i));
vec.push_back(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));
vec.push_back(interval(i, st.top(), i));
st.push(i);
}
sort(vec.begin(), vec.end(), cmp_interval);
///reverse(vec.begin(), vec.end());
for (interval cur : vec)
{
//cout << "added " << cur.left << " " << cur.right << endl;
add_range(1, 0, n + 1, cur.left, cur.right, cur);
}
}
int b[maxn];
struct node
{
int cnt, mx;
node(int _cnt = 0, int _mx = 1e9 + 10)
{
cnt = _cnt;
mx = _mx;
}
};
node tree[4 * maxn];
int lazy[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 push_lazy(int root, int left, int right)
{
tree[root].mx += lazy[root];
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
}
lazy[root] = 0;
}
void build_tree(int root, int left, int right)
{
lazy[root] = 0;
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]);
}
void update_range(int root, int left, int right, int qleft, int qright, int 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] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
node query(int root, int left, int right, int qleft, int qright)
{
push_lazy(root, left, right);
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;
build_tree(1, 1, n);
for (interval cur : ranges)
{
ll mx = min(a[cur.left], a[cur.right]);
if (range_sum(cur.left + 1, cur.right - 1) < mx)
{
update_range(1, 1, n, cur.left + 1, cur.right - 1, 1);
///cout << cur.left << " " << cur.right << endl;
//for (int i = cur.left + 1; i < cur.right; i ++)
// b[i] ++;
}
}
}
void fix_point(int pos)
{
vector < pair < int, int > > to_fix;
int root = 1, left = 0, right = n + 1;
vector < interval > to_rem;
while(true)
{
for (interval cur : act[root])
{
to_rem.push_back(cur);
if (cur.pivot == cur.left)
to_fix.push_back({cur.pivot, 0});
else
to_fix.push_back({cur.pivot, 1});
}
if (left == right)
break;
int mid = (left + right) / 2;
if (pos <= mid)
right = mid, root *= 2;
else
left = mid + 1, root = (root * 2) + 1;
}
sort(to_rem.begin(), to_rem.end(), cmp_interval);
reverse(to_rem.begin(), to_rem.end());
for (interval cur : to_rem)
{
//cout << "remove " << cur.left << " " << cur.right << endl;
// if (ranges.find(cur) == ranges.end())
// cout << "yep" << endl;
ranges.erase(cur);
rem_range(1, 0, n + 1, cur.left, cur.right, cur);
}
vector < interval > to_add;
for (pair < int, int > cur : to_fix)
{
if (cur.second == 0)
{
int df = cur.first + 1;
while(a[df] < a[cur.first])
df ++;
to_add.push_back(interval(cur.first, df, cur.first));
}
else
{
int df = cur.first - 1;
while(a[df] < a[cur.first])
df --;
to_add.push_back(interval(df, cur.first, cur.first));
}
}
sort(to_add.begin(), to_add.end(), cmp_interval);
///reverse(to_add.begin(), to_add.end());
for (interval cur : to_add)
{
ranges.insert(cur);
///cout << "added " << cur.left << " : " << cur.right << endl;
add_range(1, 0, n + 1, cur.left, cur.right, cur);
}
}
void simulate()
{
for (int i = 1; i <= n; i ++)
update_fen(i, a[i]);
get_ranges();
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;
fix_point(idx);
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
*/
