#include<bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10, M = 2e6 + 10;
int n, m, w[N];
struct bst_tree
{
    int lson, rson, fa;
    int w, size;
    void init(int fa1, int w1)
    {
        fa = fa1, w = w1, size = 1;
    }
}a[M];
int tot;
struct segment_tree
{
    int l, r;
    int root;
}b[N * 4];

inline void pushup(int p)
{
    a[p].size = a[a[p].lson].size + a[a[p].rson].size + 1;
}

inline void rotate(int x)
{
    int y = a[x].fa, z = a[y].fa;
    a[z].lson == y ? (a[z].lson = x) : (a[z].rson = x), a[x].fa = z;
    if(a[y].lson == x) a[y].lson = a[x].rson, a[a[x].rson].fa = y, a[x].rson = y, a[y].fa = x;
    else a[y].rson = a[x].lson, a[a[x].lson].fa = y, a[x].lson = y, a[y].fa = x;
    pushup(y), pushup(x);
}

inline void splay(int &root, int x, int k)
{
    while(a[x].fa != k)
    {
        int y = a[x].fa, z = a[y].fa;
        if(z != k)
            if(a[y].lson == x ^ a[z].lson == y) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(!k) root = x;
}

inline void insert(int &root, int x)
{
    int p = root, fa = 0;
    while(p) fa = p, p = x < a[p].w ? a[p].lson : a[p].rson;
    a[p = ++tot].init(fa, x);
    if(fa) x < a[fa].w ? a[fa].lson = p : a[fa].rson = p;
    splay(root, p, 0);
}

inline void erase(int &root, int x)
{
    int p = root;
    while(p)
    {
        if(a[p].w == x) break;
        p = x < a[p].w ? a[p].lson : a[p].rson;
    }
    splay(root, p, 0);
    int l = a[p].lson, r = a[p].rson;
    while(a[l].rson) l = a[l].rson;
    while(a[r].lson) r = a[r].lson;
    splay(root, l, 0), splay(root, r, l);
    a[r].lson = 0, pushup(r), pushup(l);
}

inline int getrank(int root, int x)
{
    int p = root, cnt = 0;
    while(p)
    {
        if(a[p].w < x) cnt += a[a[p].lson].size + 1, p = a[p].rson;
        else p = a[p].lson;
    }
    return cnt - 1;
}

inline int getpre(int root, int x)
{
    int p = root, pre = -INT_MAX;
    while(p)
    {
        if(a[p].w < x) pre = max(pre, a[p].w), p = a[p].rson;
        else p = a[p].lson;
    }
    return pre;
}

inline int getsuc(int root, int x)
{
    int p = root, suc = INT_MAX;
    while(p)
    {
        if(x < a[p].w) suc = min(suc, a[p].w), p = a[p].lson;
        else p = a[p].rson;
    }
    return suc;
}

inline void maketree(int p, int l, int r)
{
    b[p].l = l, b[p].r = r;
    insert(b[p].root, INT_MAX), insert(b[p].root, -INT_MAX);
    for(int i = l; i <= r; i++) insert(b[p].root, w[i]);
    if(l != r)
    {
        int mid = l + r >> 1;
        maketree(p << 1, l, mid);
        maketree(p << 1 | 1, mid + 1, r);
    }
}

inline void modify(int p, int x, int d)
{
    erase(b[p].root, w[x]), insert(b[p].root, d);
    if(b[p].l == b[p].r)
        return;
    
    int mid = b[p].l + b[p].r >> 1;
    if(x <= mid) modify(p << 1, x, d);
    else modify(p << 1 | 1, x, d);
}

inline int getrank(int p, int l, int r, int x)
{
    if(l <= b[p].l && b[p].r <= r)
        return getrank(b[p].root, x);
    
    int mid = b[p].l + b[p].r >> 1, cnt = 0;
    if(l <= mid) cnt += getrank(p << 1, l, r, x);
    if(r > mid) cnt += getrank(p << 1 | 1, l, r, x);
    return cnt;
}

inline int getpre(int p, int l, int r, int x)
{
    if(l <= b[p].l && b[p].r <= r)
        return getpre(b[p].root, x);
    
    int mid = b[p].l + b[p].r >> 1, pre = -INT_MAX;
    if(l <= mid) pre = max(pre, getpre(p << 1, l, r, x));
    if(r > mid) pre = max(pre, getpre(p << 1 | 1, l, r, x));
    return pre;
}

inline int getsuc(int p, int l, int r, int x)
{
    if(l <= b[p].l && b[p].r <= r)
        return getsuc(b[p].root, x);
    
    int mid = b[p].l + b[p].r >> 1, suc = INT_MAX;
    if(l <= mid) suc = min(suc, getsuc(p << 1, l, r, x));
    if(r > mid) suc = min(suc, getsuc(p << 1 | 1, l, r, x));
    return suc;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    maketree(1, 1, n);
    
    while(m--)
    {
        int op, l, r, x;
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1) scanf("%d", &x), printf("%d\n", getrank(1, l, r, x) + 1);
        if(op == 2)
        {
            scanf("%d", &x);
            int l1 = 0, r1 = 1e8;
            while(l1 < r1)
            {
                int mid = l1 + r1 + 1 >> 1;
                if(getrank(1, l, r, mid) + 1 <= x) l1 = mid;
                else r1 = mid - 1;
            }
            printf("%d\n", l1);
        }
        if(op == 3) modify(1, l, r), w[l] = r;
        if(op == 4) scanf("%d", &x), printf("%d\n", getpre(1, l, r, x));
        if(op == 5) scanf("%d", &x), printf("%d\n", getsuc(1, l, r, x));
    }
}