#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e4 + 5, maxm = 1e7;
const int inf = 0x7fffffff;
int a[maxn], n, m, cnt;
namespace treap{
    struct fhq_node{
        int l, r;
        int key, val;
        int siz;
    }t[maxm];
    struct fhq_treap{
        int root;
        inline void update(int p){
            t[p].siz = t[t[p].l].siz + t[t[p].r].siz + 1;
        }
        inline int new_node(int x){
            ++cnt; t[cnt].l = t[cnt].r = 0;
            t[cnt].siz = 1; t[cnt].key = rand();
            t[cnt].val = x; return cnt;
        }
        inline int merge(int l, int r){
            if(!l || !r) return l + r;
            if(t[l].key <= t[r].key){
                t[l].r = merge(t[l].r, r);
                update(l); return l;
            }else{
                t[r].l = merge(l, t[r].l);
                update(r); return r;
            }
        }
        inline void split(int p, int k, int &l, int &r){
            if(!p) return void(l = r = 0);
            if(t[p].val <= k){
                l = p; split(t[p].r, k, t[p].r, r);
            }else{
                r = p; split(t[p].l, k, l, t[p].l);
            } update(p);
        }
        inline void ins(int x){
            int l, r; split(root, x, l, r);
            root = merge(merge(l, new_node(x)), r);
        }
        inline void build(int l, int r){
            for(int i = l; i <= r; i++) ins(a[i]);
            return;
        }
        inline void del(int x){ int l, r, p;
            split(root, x, l, r);
            split(l, x - 1, l, p);
            p = merge(t[p].l, t[p].r);
            root = merge(merge(l, p), r);
        }
        inline int rnk(int x){ int l, r;
            split(root, x - 1, l, r);
            int res = t[l].siz + 1;
            root = merge(l, r);
            return res;
        }
        inline int kth(int p, int k){
            if(k <= t[t[p].l].siz) return kth(t[p].l, k);
            if(k == t[t[p].l].siz + 1) return t[p].val;
            k -= (t[t[p].l].siz + 1); return kth(t[p].r, k);
        }
        inline int pre(int x){ int l, r;
            split(root, x - 1, l, r);
            int res = kth(l, t[l].siz);
            root = merge(l, r); return res;
        }
        inline int nxt(int x){ int l, r;
            split(root, x, l, r);
            int res = kth(r, 1);
            root = merge(l, r); return res;
        }
    } T[maxn << 2];
}
namespace seg_tree{
    inline void insert(int p, int l, int r){
        treap::T[p].build(l, r);
        if(l == r) return;
        int mid = (l + r) >> 1;
        insert(p * 2, l, mid);
        insert(p * 2 + 1, mid + 1, r);
        return;
    }
    int rnk(int p, int l, int r, int L, int R, int k){ // l, r:segment tree; L, R: a_l - a_r
        if(r < L || l > R) return 0;
        if(l >= L && r <= R) return treap::T[p].rnk(k) - 1;
        int mid = (l + r) >> 1;
        return rnk(p * 2, l, mid, L, R, k) + rnk(p * 2 + 1, mid + 1, r, L, R, k);
    }
    int kth(int l, int r, int k){
        int x = 0, y = 1e8, ans = -1;
        while(x <= y){
            int mid = (x + y) >> 1;
            if(rnk(1, 1, n, l, r, mid) + 1 <= k) ans = mid, x = mid + 1;
            else y = mid - 1;
        }return ans;
    }
    inline void update(int p, int l, int r, int pos, int k){
        treap::T[p].del(a[pos]); treap::T[p].ins(k);
        if(l != r){
            int mid = (l + r) >> 1;
            if(pos <= mid) update(p * 2, l, mid, pos, k);
            else update(p * 2 + 1, mid + 1, r, pos, k);
        }return;
    }
    inline int pre(int p, int l, int r, int L, int R, int k){
        if(r < L || l > R) return -inf;
        if(l >= L && r <= R) return treap::T[p].pre(k);
        int mid = (l + r) >> 1;
        return max(pre(p * 2, l, mid, L, R, k), pre(p * 2 + 1, mid + 1, r, L, R, k));
    } 
    inline int nxt(int p, int l, int r, int L, int R, int k){
        if(r < L || l > R) return inf;
        if(l >= L && r <= R) return treap::T[p].nxt(k);
        int mid = (l + r) >> 1;
        return min(nxt(p * 2, l, mid, L, R, k), nxt(p * 2 + 1, mid + 1, r, L, R, k));
    }
}
signed main(){ srand(time(0));
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    seg_tree::insert(1, 1, n);
    while(m--){ int opt, l, r, k;
        cin >> opt;
        if(opt == 1){
            cin >> l >> r >> k;
            cout << seg_tree::rnk(1, 1, n, l, r, k) + 1 << '\n';
        }else if(opt == 2){
            cin >> l >> r >> k;
            cout << seg_tree::kth(l, r, k) << '\n';
        }else if(opt == 3){
            cin >> l >> k;
            seg_tree::update(1, 1, n, l, k);
        }else if(opt == 4){
            cin >> l >> r >> k;
            cout << seg_tree::pre(1, 1, n, l, r, k) << '\n';
        }else{
            cin >> l >> r >> k;
            cout << seg_tree::nxt(1, 1, n, l, r, k) << '\n';
        }
    }return 0;   
}

求前驱后继时查着查着p和l就成了0了。调了好久没调出来。有哪位大佬能帮我调一调啊。悬关