数据结构简单题。
考虑到排序是个很麻烦的事情，很难维护这种操作。但发现题目中没有修改操作，所以考虑直接离线。
离线之后做什么呢？容易想到二分答案 $x$，然后把 $\leq x$ 的数改为 $0$，$\gt x$ 的数改为 $1$。
这样减掉了大量的无用状态，即我们只需要知道 $0,1$ 之间的相对大小即可。
那么每次把一段区间排序就是简单的，直接前缀后缀覆盖 $0,1$ 即可。

注意如果区间内没有 $0,1$ 那么区间长度为 $0$，可能造成线段树越界。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
int n, m, pos, a[N];
struct node {
    int op, l, r;
} q[N];

struct Tree {
    int l, r;
    int c0, c1;
    bool f0, f1;
} tr[N << 2];

void pushup(int u) {
    tr[u].c0 = tr[u << 1].c0 + tr[u << 1 | 1].c0;
    tr[u].c1 = tr[u << 1].c1 + tr[u << 1 | 1].c1;
}
void pushdown(int u) {
    if (tr[u].f0) {
        tr[u << 1].f1 = 0, tr[u << 1].f0 = 1;
        tr[u << 1 | 1].f1 = 0, tr[u << 1 | 1].f0 = 1;
        tr[u << 1].c1 = 0, tr[u << 1].c0 = (tr[u << 1].r - tr[u << 1].l + 1);
        tr[u << 1 | 1].c1 = 0, tr[u << 1 | 1].c0 = (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
        tr[u].f0 = 0;
    }
    if (tr[u].f1) {
        tr[u << 1].f0 = 0, tr[u << 1].f1 = 1;
        tr[u << 1 | 1].f0 = 0, tr[u << 1 | 1].f1 = 1;
        tr[u << 1].c0 = 0, tr[u << 1].c1 = (tr[u << 1].r - tr[u << 1].l + 1);
        tr[u << 1 | 1].c0 = 0, tr[u << 1 | 1].c1 = (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
        tr[u].f1 = 0;
    }
}

void build(int u, int l, int r, int x) {
    tr[u].l = l, tr[u].r = r;
    tr[u].f0 = tr[u].f1 = 0;
    if (l == r) {
        tr[u].c0 = (a[l] <= x);
        tr[u].c1 = (a[l] > x);
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid, x);
    build(u << 1 | 1, mid + 1, r, x);
    pushup(u);
}

void change(int u, int d) {
    if (d == 0) {
        tr[u].c0 = tr[u].r - tr[u].l + 1;
        tr[u].c1 = 0;
        tr[u].f0 = 1, tr[u].f1 = 0;
    } else {
        tr[u].c1 = tr[u].r - tr[u].l + 1;
        tr[u].c0 = 0;
        tr[u].f1 = 1, tr[u].f0 = 0;
    }
}
void cover(int u, int l, int r, int d) {
    if (l > r) return;
    if (tr[u].l >= l && tr[u].r <= r) return change(u, d);
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) cover(u << 1, l, r, d);
    if (r > mid) cover(u << 1 | 1, l, r, d);
    pushup(u);
}
int query(int u, int l, int r, int d) {
    if (l > r) return 0;
    if (tr[u].l >= l && tr[u].r <= r) return (d == 0) ? tr[u].c0 : tr[u].c1;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int res = 0;
    if (l <= mid) res += query(u << 1, l, r, d);
    if (r > mid) res += query(u << 1 | 1, l, r, d);
    return res;
}
int ask(int u, int x) {
    if (tr[u].l == tr[u].r) return tr[u].c1;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) return ask(u << 1, x);
    return ask(u << 1 | 1, x);
}

bool check(int x) {
    build(1, 1, n, x);
    for (int i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r;
        if (q[i].op == 0) { //升序
            int cnt0 = query(1, l, r, 0), cnt1 = (r - l + 1) - cnt0;
            cover(1, l, l + cnt0 - 1, 0), cover(1, l + cnt0, r, 1);
        } else {    //降序
            int cnt0 = query(1, l, r, 0), cnt1 = (r - l + 1) - cnt0;
            cover(1, l, l + cnt1 - 1, 1), cover(1, l + cnt1, r, 0);
        }
    }
    // for (int i = 1; i <= n; i++) cout << ask(1, i) << ' '; puts("");
    return ask(1, pos);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) scanf("%d%d%d", &q[i].op, &q[i].l, &q[i].r);
    scanf("%d", &pos);
    int l = 1, r = n;
    // for (int i = 1; i <= n; i++) check(i);
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) l = mid + 1;
        else r = mid;
    }
    printf("%d\n", l);
    return 0;
}