代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int M = 3e6 + 5;

int n, m;
int a[N];

struct Node{
  int ls, rs;
  int val, key;
  int size;
}tree[M];

int tot;

struct FHQ_Treap{
	int root;
	
	inline int newnode(int val){
	  tot++;
	  tree[tot].val = val;
	  tree[tot].ls = 0;
	  tree[tot].rs = 0;
	  tree[tot].key = rand();
	  tree[tot].size = 1;
	  return tot;
	}
	
	inline void update(int node){
	  tree[node].size = tree[tree[node].ls].size + tree[tree[node].rs].size + 1;
	}
	
	void split(int node, int val, int &r1, int &r2){
	  if(!node){
	    r1 = 0;
	    r2 = 0;
	    return ;
	  }
	  if(tree[node].val <= val){
	    r1 = node;
	    split(tree[node].rs, val, tree[node].rs, r2);
	  }
	  else{
	    r2 = node;
	    split(tree[node].ls, val, r1, tree[node].ls);
	  }
	  update(node);
	}
	
	int merge(int x, int y){
	  if(!x || !y){
	    return x + y;
	  }
	  if(tree[x].key > tree[y].key){
	    tree[x].rs = merge(tree[x].rs, y);
	    update(x);
	    return x;
	  }
	  else{
	    tree[y].ls = merge(x, tree[y].ls);
	    update(y);
	    return y;
	  }
	}
	
	int t1, t2, t3;
	
	inline void insert(int val){
	  split(root, val, t1, t2);
	  root = merge(merge(t1, newnode(val)), t2);
	}
	
	inline void _delete(int val){
	  split(root, val, t1, t3);
	  split(t1, val - 1, t1, t2);
	  t2 = merge(tree[t2].ls, tree[t2].rs);
	  root = merge(merge(t1, t2), t3);
	}
	
	inline int _rank(int val){
	  split(root, val - 1, t1, t2);
	  int ans = tree[t1].size + 1;
	  root = merge(t1, t2);
	  return ans;
	}
	
	inline int query(int rank){
	  int node = root;
	  while(node){
	    if(tree[tree[node].ls].size + 1 == rank){
	      break;
	    }
	    else if(tree[tree[node].ls].size >= rank){
	      node = tree[node].ls;
	    }
	    else{
	      rank -= tree[tree[node].ls].size + 1;
	      node = tree[node].rs;
	    }
	  }
	  return tree[node].val;
	}
	
	inline int pre(int val){
	  split(root, val - 1, t1, t2);
	  int node = t1;
	  while(tree[node].rs){
	    node = tree[node].rs;
	  }
	  int ans = (!tree[t1].size ? -2147483647 : tree[node].val);
	  root = merge(t1, t2);
	  return ans;
	}
	
	inline int nxt(int val){
	  split(root, val, t1, t2);
	  int node = t2;
	  while(tree[node].ls){
	    node = tree[node].ls;
	  }
	  int ans = (!tree[t2].size ? 2147483647 : tree[node].val);
	  root = merge(t1, t2);
	  return ans;
	}
	
	inline build(int l, int r){
		for(int i = l; i <= r; i++){
			insert(a[i]);
		}
	}
}ft[M];

struct Segment_Tree{
	void build(int node, int lt, int rt){
		ft[node].build(lt, rt);
		if(lt == rt){
			return ;
		}
		int mid = lt + rt >> 1;
		build(node << 1, lt, mid);
		build(node << 1 | 1, mid + 1, rt);
	}
	
	int rank_(int node, int lt, int rt, int x, int y, int val){
		if(y < lt || x > rt){
			return 0;
		}
		if(x <= lt && rt <= y){
			return ft[node]._rank(val) - 1;
		}
		int mid = lt + rt >> 1;
		return rank_(node << 1, lt, mid, x, y, val) + rank_(node << 1 | 1, mid + 1, rt, x, y, val);
	}
	
	int query(int x, int y, int val){
		int l = 0, r = 1e8, ans = -1;
		while(l <= r){
			int mid = l + r >> 1;
			if(rank_(1, 1, n, l, r, mid) + 1 <= val){
				ans = mid;
				l = mid + 1;
			}
			else{
				r = mid - 1;
			}
		}
		return ans;
	}
	
	void update(int node, int lt, int rt, int x, int val){
		if(x < lt || x > rt){
			return ;
		}
		ft[node]._delete(a[x]);
		ft[node].insert(val);
		if(lt == rt){
			return ;
		}
		int mid = lt + rt >> 1;
		update(node << 1, lt, mid, x, val);
		update(node << 1 | 1, mid + 1, rt, x, val);
	}
	
	int pre(int node, int lt, int rt, int x, int y, int val){
		if(y < lt || x > rt){
			return -2147483647;
		}
		if(x <= lt && rt <= y){
			return ft[node].pre(val);
		}
		int mid = lt + rt >> 1;
		return max(pre(node << 1, lt, mid, x, y, val), pre(node << 1 | 1, mid + 1, rt, x, y, val));
	}
	
	inline int nxt(int node, int lt, int rt, int x, int y, int val){
    if(y < lt || x > rt){
      return 2147483647;
    }
    if(x <= lt && rt <= y){
      return ft[node].nxt(val);
    }
    int mid = lt + rt >> 1;
    return min(nxt(node << 1, lt, mid, x, y, val), nxt(node << 1 | 1, mid + 1, rt, x, y, val));
  }
}T;

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	T.build(1, 1, n);
	while(m--){
		int op;
		cin >> op;
		if(op == 1){
			int l, r, k;
			cin >> l >> r >> k;
			cout << T.rank_(1, 1, n, l, r, k) + 1 << '\n';
		}
		else if(op == 2){
			int l, r, k;
			cin >> l >> r >> k;
			cout << T.query(l, r, k) << '\n';
		}
		else if(op == 3){
			int x, val;
			cin >> x >> val;
			T.update(1, 1, n, x, val);
			a[x] = val;
		}
		else if(op == 4){
			int l, r, k;
			cin >> l >> r >> k;
			cout << T.pre(1, 1, n, l, r, k) << '\n';
		}
		else{
			int l, r, k;
			cin >> l >> r >> k;
			cout << T.nxt(1, 1, n, l, r, k) << '\n';
		}
	}
	return 0;
}