记得当年省选的时候 这道题连暴力都没写对（尴尬ing）

（当年天真的认为sort是左闭右闭的hhhhhh）

思路：

首先 二分答案

线段树

首先二分答案，然后需要知道进行m次排序后p位置上的数字是否大于mid。

对于一个mid，我们可以把序列里的数字分为两类，即大于mid的数和小于等于mid的数，分别用1和0表示。

对这些0和1进行排序时，对于一个区间[l,r]进行升序排序，等价于把所有的0放在前面，所有的1放在后面；降序排序反之。

用线段树支持区间求和及区间修改即可。

                                             -----YOUSIKI

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 100050

int n,m,a[N],askx[N],asky[N],op[N],l=1,r,xx,tree[N*16],lazy[N*16],ans;

void insert(int l,int r,int pos,int id,int wei){

    if(l==r){tree[pos]+=wei;return;}

    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;

    if(mid<id)insert(mid+1,r,rson,id,wei);

    else insert(l,mid,lson,id,wei);

    tree[pos]=tree[lson]+tree[rson];

}

void push_down(int pos,int num){

    int lson=pos<<1,rson=pos<<1|1;

    tree[lson]=(num-num/2)*lazy[pos],tree[rson]=(num>>1)*lazy[pos];

    lazy[lson]=lazy[rson]=lazy[pos];

    lazy[pos]=-1;

}

int query(int l,int r,int pos,int L,int R){

    if(~lazy[pos])push_down(pos,r-l+1);

    if(l>=L&&r<=R)return tree[pos];

    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;

    if(mid<L)return query(mid+1,r,rson,L,R);

    else if(mid>=R)return query(l,mid,lson,L,R);

    else return query(l,mid,lson,L,R)+query(mid+1,r,rson,L,R);

}

void modify(int l,int r,int pos,int L,int R,int wei){

    if(L>R)return;

    if(l>=L&&r<=R){tree[pos]=(r-l+1)*wei,lazy[pos]=wei;return;}

    if(~lazy[pos])push_down(pos,r-l+1);

    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;

    if(mid<L)modify(mid+1,r,rson,L,R,wei);

    else if(mid>=R)modify(l,mid,lson,L,R,wei);

    else modify(l,mid,lson,L,R,wei),modify(mid+1,r,rson,L,R,wei);

    tree[pos]=tree[lson]+tree[rson];

}

int main(){

    scanf("%d%d",&n,&m),r=n;

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    for(int i=1;i<=m;i++)scanf("%d%d%d",&op[i],&askx[i],&asky[i]);

    scanf("%d",&xx);

    while(l<=r){

        memset(tree,0,sizeof(tree)),memset(lazy,-1,sizeof(lazy));

        int mid=(l+r)>>1;

        for(int i=1;i<=n;i++)insert(1,n,1,i,a[i]<=mid);

        for(int i=1;i<=m;i++){

            int num=query(1,n,1,askx[i],asky[i]);

            modify(1,n,1,askx[i],asky[i],0);

            if(!op[i])modify(1,n,1,askx[i],askx[i]+num-1,1);

            else modify(1,n,1,asky[i]-num+1,asky[i],1);

        }

        if(query(1,n,1,xx,xx))r=mid-1,ans=mid;

        else l=mid+1;

    }

    printf("%d\n",ans);

}