遅延セグメント木を用いてこの問題を解くことができます。

\(\displaystyle \sum_{j\geq i} d[j]\) が区間 \(i\) の右端の座標と一致するような \(d\) を遅延セグメント木で管理することを考えます。左端も同様です。すると、各区間に対する処理は \([0,v)\) に対する区間作用として表すことができ、さらに解答クエリも遅延セグメント木上の二分探索を行うことで各クエリ \(O(\log N)\) 時間で処理することができます。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N+Q\log N)\) です。詳しくは実装例を参考にしてください。

実装例(C++)

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
struct S {
	int x;
	int y;
};
S op(S c1, S c2) { return {c1.x + c2.x, c1.y + c2.y}; }
S e() { return {0, 0}; }
using F = int;
S mapping(F f, S c) {
	if (f == 0)
		c.x = 0;
	if (f == 1)
		c.x = c.y;
	return c;
}
F composition(F f, F g) { return f == -1 ? g : f; }
F id() { return -1; }
int x;
bool ga(S c) { return c.x <= x; }
int y;
bool gb(S c) { return c.x > y; }
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> w(n);
	for (int &i : w) cin >> i;
	vector<int> a(n);
	rep(i, n - 1) a[i + 1] = w[n - i - 1] - w[n - i - 2];
	vector<S> to_sega(n), to_segb(n);
	rep(i, n) {
		to_sega[i] = {0, a[i]};
		to_segb[i] = {-a[i], -a[i]};
	}
	atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg_a(to_sega), seg_b(to_segb);
	int que;
	cin >> que;
	while (que--) {
		int ty;
		cin >> ty;
		if (ty == 1) {
			int v;
			cin >> v;
			v = n - v + 1;
			seg_a.apply(v, n, 0);
			seg_b.apply(v, n, 1);
			continue;
		}
		if (ty == 2) {
			int v;
			cin >> v;
			v = n - v + 1;
			seg_a.apply(v, n, 1);
			seg_b.apply(v, n, 0);
			continue;
		}
		cin >> x;
		y = x - w[n - 1];
		if (y >= 0) {
			cout << 0 << endl;
			continue;
		}
		cout << min(seg_a.max_right<ga>(0), seg_b.max_right<gb>(0)) << endl;
	}
}