#include<bits/stdc++.h>
using namespace std;
long long n, m, a[100005], q, op[100005], x[100005], y[100005];
struct node{
    long long l, r, sum, lazy;
}f[400005];
void build(int l, int r, int t, int id){
    f[id].l = l, f[id].r = r;
    if(l == r){
        if(a[l] >= t)
            f[id].sum = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, t, id * 2);
    build(mid + 1, r, t, id * 2 + 1);
    f[id].sum = f[id * 2].sum + f[id * 2 + 1].sum;
}
void pushdown(int id){
    f[id * 2].lazy = f[id].lazy;
    f[id * 2 + 1].lazy = f[id].lazy;
    if(f[id].lazy != -1)
        f[id * 2].lazy = f[id].lazy, f[id * 2 + 1].lazy = f[id].lazy, f[id * 2].sum = (f[id * 2].r - f[id * 2].l + 1) * f[id].lazy, f[id * 2 + 1].sum = (f[id * 2 + 1].r - f[id * 2 + 1].l + 1) * f[id].lazy;
}
int query(int l, int r, int id){
    if(l == f[id].l && r == f[id].r)
        return f[id].sum;
    pushdown(id);
    if(r <= f[id * 2].r)
        return query(l, r, id * 2);
    else
        if(l >= f[id * 2 + 1].l)
            return query(l, r, id * 2 + 1);
        else
            return query(l, f[id * 2].r, id * 2) + query(f[id * 2 + 1].l, r, id * 2 + 1);
    f[id].sum = f[id * 2].sum + f[id * 2 + 1].sum;
    if(f[id * 2].lazy == f[id * 2 + 1].lazy)
        f[id].lazy = f[id * 2].lazy;
    else
        f[id].lazy = -1;
    f[id].sum = f[id * 2].sum + f[id * 2 + 1].sum;
    if(f[id * 2].lazy == f[id * 2 + 1].lazy)
        f[id].lazy = f[id * 2].lazy;
    else
        f[id].lazy = -1;
}
void change(int l, int r, int t, int id){
    if(l == f[id].l && r == f[id].r){
        f[id].sum = (f[id].r - f[id].l + 1) * t;
        f[id].lazy = t;
        cout<<l<<' '<<r<<' '<<t<<' '<<id<<' '<<f[id].l<<' '<<f[id].r<<' '<<f[id].sum<<' '<<f[id].lazy<<endl;
        return;
    }
    if(l > f[id].r || r < f[id].l)
        return;
    pushdown(id);
    if(r <= f[id * 2].r)
        change(l, r, t, id * 2);
    else
        if(l >= f[id * 2 + 1].l)
            change(l, r, t, id * 2 + 1);
        else
            change(l, f[id * 2].r, t, id * 2), change(f[id * 2 + 1].l, r, t, id * 2 + 1);
    f[id].sum = f[id * 2].sum + f[id * 2 + 1].sum;
    if(f[id * 2].lazy == f[id * 2 + 1].lazy)
        f[id].lazy = f[id * 2].lazy;
    else
        f[id].lazy = -1;
    cout<<l<<' '<<r<<' '<<t<<' '<<id<<' '<<f[id].l<<' '<<f[id].r<<' '<<f[id].sum<<' '<<f[id].lazy<<endl;
}
void oper(int t){
    for(int i = 1;i <= 400003;i++)
        f[i].sum = 0, f[i].lazy = -1;
    build(1, n, t, 1);
    for(int i = 1;i <= m;i++){
        int s = query(x[i], y[i], 1);
        cout<<s<<endl;
        if(op[i] == 1){
            if(s <= y[i] - x[i] && s){
                change(x[i], y[i] - s, 1, 1);
            cout<<endl;
                change(y[i] - s + 1, y[i], 0, 1);
            }
        }
        else{
            if(s <= y[i] - x[i] && s){
                change(x[i], x[i] + s - 1, 0, 1);
                cout<<endl;
                change(x[i] + s, y[i], 1, 1);
            }
        }
        cout<<endl;
    }
    //for(int i = 1;i <= 4 * n;i++)
        //cout<<t<<' '<<f[i].l<<' '<<f[i].r<<' '<<f[i].sum<<endl;
}
int main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
        cin>>a[i];
    for(int i = 1;i <= m;i++)
        cin>>op[i]>>x[i]>>y[i];
    cin>>q;
    int left = 1, right = n, middle, ans = 0;
    while(left <= right){
        middle = left + (right - left) / 2;
        oper(middle);
        //cout<<left<<' '<<right<<' '<<middle<<' '<<ans<<' '<<query(q, q, 1)<<endl;
        if(query(q, q, 1) == 1){
            left = middle + 1, ans = middle;
        }
        else
            right = middle - 1;
    }
    cout<<middle;
    return 0;
}