考虑二分，若 $mid$ 为当前二分到的数，则把 $\le mid$ 的数设成 $0$，另外的设成 $1$，升序排序相当于把 $0$ 移到最前面，降序相当于把 $1$ 移动到最后面（再该区间范围内）。

还是很简单的 QwQ。

code：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	register char in = getchar(),f = 0;register int t = 0;
	for(;!isdigit(in);in = getchar())if(!(in ^ 45)) f = 1;
	for(;in >= '0' && in <= '9';in = getchar())
	 t = (t << 1) + (t << 3) + (in ^ 48);
	return f ? -t : t;
}
inline void write(register int x)
{
	static int t[25];register int tp = 0;
	if(x == 0) return (void) (puts("0"));
	else if(x < 0) putchar('-'),x = -x;
	while(x) t[++tp] = x % 10,x /= 10;
	while(tp) putchar(t[tp--] + '0');
	puts("");
}
#define stdi stdin
#define stdo stdout
int n = read(),m = read(),a[100012],ans,q;
struct input
{
	int k,l,r;
}s[100012];
struct node
{
	int l,r;
	mutable int v;
	node(int l,int r = 0,int v = 0) : l(l),r(r),v(v){}
	bool operator < (const node &other)const { return l < other.l; }
};set<node> tree;
inline set<node> :: iterator split(register int pos)
{
	register set<node> :: iterator it = tree.lower_bound(node(pos));
	if(it != tree.end() && it -> l == pos) return it; it--;
	if(it -> r < pos) return tree.end();
	register int l = it -> l;
	register int r = it -> r;
	register int v = it -> v;
	tree.erase(it);
	tree.insert(node(l,pos - 1,v));
	return tree.insert(node(pos,r,v)).first;
}
inline int find(register int l,register int r)
{
	register int ret = 0;
	set<node> :: iterator rr = split(r + 1),ll = split(l),it;
	for(it = ll;it != rr;it++)
	{
		if(it -> v) ret += it -> r - it -> l + 1;
	}
	return ret;
}
void amend(register int l,register int r,register int k)
{
	set<node> :: iterator rr = split(r + 1),ll = split(l);
	tree.erase(ll,rr),tree.insert(node(l,r,k)); return;
}
inline short check(int mid)
{
	tree.clear();
	for(int i = 1;i <= n;i++) tree.insert(node(i,i,a[i] >= mid));
	for(int i = 1;i <= m;i++)
	{
		register int op = s[i].k,l = s[i].l,r = s[i].r,M = find(l,r);
		if(op == 0) amend(l,r - M,0),amend(r - M + 1,r,1);
		if(op == 1) amend(l,l + M - 1,1),amend(l + M,r,0);
	}
	return split(q) -> v == 1;
}
int main()
{
	setvbuf(stdi,(char*)calloc(1 << 20,sizeof(char)),_IOFBF,1 << 20);
	setvbuf(stdo,(char*)calloc(1 << 20,sizeof(char)),_IOFBF,1 << 20);
	for(int i = 1;i <= n;i++) a[i] = read();
	for(int i = 1;i <= m;i++)
	{
		s[i].k = read();
		s[i].l = read();
		s[i].r = read();
	}
	q = read();
	int l = 1,r = n,mid;
	while(l <= r)
	{
		mid = l + r >> 1;
		if(check(mid)) ans = mid,l = mid + 1;
		else r = mid - 1;
	}
	write(ans);
}