TLE #1 #10 #11。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
inline void read(int &x) {
	x = 0;
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
}
inline void write(const int &x) {
	if (x >= 10) write(x / 10);
	putchar(x % 10 + 48);
}
int n, m, q, a[N], b[N], op[N], l[N], r[N];
struct Segment_Tree {
#define ls (x << 1)
#define rs (x << 1 | 1)
	
	struct node {
		int sum, lazy;
	} t[N << 3];
	inline void PushUp(int x) {
		t[x].sum = t[ls].sum + t[rs].sum;
	}
	inline void PushDown(int x, int l, int r) {
		int mid = (l + r) >> 1;
		if (t[x].lazy == -1) {
			t[ls].lazy = t[rs].lazy = -1;
			t[ls].sum = t[rs].sum = 0;
		}
		else if (t[x].lazy == 1) {
			t[ls].lazy = t[rs].lazy = 1;
			t[ls].sum = mid - l + 1;
			t[rs].sum = r - mid;
		}
		t[x].lazy = 0;
	}
	void Build(int x, int l, int r) {
		int mid = (l + r) >> 1;
		t[x].lazy = 0;
		if (l == r) {
			t[x].sum = b[mid];
			return;
		}
		Build(ls, l, mid);
		Build(rs, mid + 1, r);
		PushUp(x);
	}
	int Query(int x, int l, int r, int ql, int qr) {
		if (l == r)
			return t[x].sum;
		int mid = (l + r) >> 1;
		PushDown(x, l, r);
		int ans = 0;
		if (ql <= mid)
			ans += Query(ls, l, mid, ql, qr);
		if (mid + 1 <= qr)
			ans += Query(rs, mid + 1, r, ql, qr);
		return ans;
	}
	void Modify(int x, int l, int r, int ql, int qr, int q) {
	    if (ql > qr) return;
	    if (ql > r || qr < l) return;
		if (ql <= l && r <= qr) {
			if (q == 0)
				t[x].lazy = -1, t[x].sum = 0;
			else
				t[x].lazy = 1, t[x].sum = r - l + 1;
			return;
		}
		int mid = (l + r) >> 1;
		PushDown(x, l, r);
		if (ql <= mid)
			Modify(ls, l, mid, ql, qr, q);
		if (mid + 1 <= qr)
			Modify(rs, mid + 1, r, ql, qr, q);
		PushUp(x);
	}
	
#undef ls
#undef rs
};
Segment_Tree tree;
inline bool check(int mid) {
	for (int i = 1; i <= n; i++)
		b[i] = (a[i] >= mid);
	tree.Build(1, 1, n);
	for (int i = 1; i <= m; i++) {
		int cnt = tree.Query(1, 1, n, l[i], r[i]);
		if (op[i] == 0)
			tree.Modify(1, 1, n, l[i], r[i] - cnt, 0),
			tree.Modify(1, 1, n, r[i] - cnt + 1, r[i], 1);
		else
			tree.Modify(1, 1, n, l[i] + cnt, r[i], 0),
			tree.Modify(1, 1, n, l[i], l[i] + cnt - 1, 1);
	}
	return tree.Query(1, 1, n, q, q);
}
int main(int argc, char* argv[]) {
	read(n), read(m);
	for (int i = 1; i <= n; i++)
		read(a[i]);
	for (int i = 1; i <= m; i++)
		read(op[i]), read(l[i]), read(r[i]);
	read(q);
	int l = 1, r = n, mid, ans = -1;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	write(ans), putchar('\n');
	return 0; 
}