RT

#include <bits/stdc++.h>
using namespace std;
const int N=2000005,INF=0x7fffffff;
int a[N],n,q,mx,mn=INF;
struct Splay
{
	int c[N][2],cs[N][2],v[N],cnt[N],prt[N],p,q,sz;
	inline int sum(int x) {return x?cs[x][0]+cs[x][1]+cnt[x]:0;}
	void rot(int x)
	{
		int fa=prt[x],gr=prt[fa],s=c[fa][1]==x,son=c[x][!s];
		c[fa][s]=son;
		prt[son]=fa;
		cs[fa][s]=sum(son);
		c[prt[x]=gr][c[gr][1]==fa]=x;
		c[prt[fa]=x][!s]=fa;
		cs[x][!s]=sum(fa);
	}
	void splay(int &rt,int x)
	{
		while(prt[x])
		{
			int fa=prt[x],gr=prt[fa];
			if(gr&&(c[gr][1]==fa)==(c[fa][1]==x)) rot(fa);
			rot(x);
		}
		rt=x;
	}
	void find(int rt,int x)
	{
		v[q=0]=x; p=rt;
		while(v[p]!=x) q=p,p=c[p][x>v[p]];
	}
	void insert(int &rt,int x)
	{
		find(rt,x);
		if(p) {cnt[p]++; splay(rt,p); return;}
		v[++sz]=x;
		c[prt[sz]=q][x>v[q]]=sz;
		cs[q][x>v[q]]=1;
		splay(rt,sz);
		cnt[sz]=1;
	}
	void del(int &rt,int x)
	{
		find(rt,x);
		if(!p) return;
		cnt[p]--; splay(rt,p);
		if(cnt[p]) return;
		for(int i=0;i<=1;i++)
			if(!c[p][i]) {prt[rt=c[p][!i]]=0; return;}
		prt[rt=q=c[p][0]]=0;
		while(c[q][1]) q=c[q][1];
		splay(rt,q);
		prt[c[q][1]=c[p][1]]=q;
		cs[q][1]=cs[p][1];
	}
	int ask(int rt,int x)
	{
		p=rt;
		int res=0;
		while(p)
		{
			if(x>=v[p]) res+=cnt[p]+cs[p][0];
			p=c[p][x>=v[p]];
		}
		return res;
	}
	int ask2(int rt,int x)
	{
		p=rt;
		int res=0;
		while(p)
		{
			if(x==v[p]) return res+cs[p][0];
			if(x>v[p]) res+=cnt[p]+cs[p][0];
			p=c[p][x>v[p]];
		}
		return res;
	}
	int nxt(int &rt,int x)
	{
		insert(rt,x);
		int y=c[rt][1]; del(rt,x);
		if(!y) {del(rt,x); return INF;}
		while(c[y][0]) y=c[y][0];
		del(rt,x);
		return v[y];
	}
	int lst(int &rt,int x)
	{
		insert(rt,x);
		int y=c[rt][0];
		if(!y) {del(rt,x); return -INF;}
		while(c[y][1]) y=c[y][1];
		del(rt,x);
		return v[y];
	}
}s;
struct segTree
{
	struct node {int l,r,rt;}t[N<<2];
	void build(int x,int l,int r)
	{
		t[x].l=l; t[x].r=r;
		for(int i=l;i<=r;i++) s.insert(t[x].rt,a[i]);
		if(l==r) return;
		int mid=l+r>>1;
		build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
	}
	void change(int x,int y,int z)
	{
		if(t[x].r<y||t[x].l>y) return;
		s.del(t[x].rt,a[y]);
		s.insert(t[x].rt,z);
		change(x<<1,y,z);
		change(x<<1|1,y,z);
	}
	int ask(int x,int l,int r,int y)
	{
		if(t[x].r<l||t[x].l>r) return 0;
		if(l<=t[x].l&&r>=t[x].r) return s.ask(t[x].rt,y);
		return ask(x<<1,l,r,y)+ask(x<<1|1,l,r,y);
	}
	int lst(int x,int l,int r,int y)
	{
		if(t[x].r<l||t[x].l>r) return -INF;
		if(l<=t[x].l&&r>=t[x].r) return s.lst(t[x].rt,y);
		return max(lst(x<<1,l,r,y),lst(x<<1|1,l,r,y));
	}
	int nxt(int x,int l,int r,int y)
	{
		if(t[x].r<l||t[x].l>r) return INF;
		if(l<=t[x].l&&r>=t[x].r) return s.nxt(t[x].rt,y);
		return min(nxt(x<<1,l,r,y),nxt(x<<1|1,l,r,y));
	}
	int ask2(int x,int l,int r,int y)
	{
		if(t[x].r<l||t[x].l>r) return 0;
		if(l<=t[x].l&&r>=t[x].r) return s.ask2(t[x].rt,y);
		return ask2(x<<1,l,r,y)+ask2(x<<1|1,l,r,y);
	}
}t;
int main()
{
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	t.build(1,1,n);
	int op,x,y,z;
	while(q--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d %d %d",&x,&y,&z);
			printf("%d\n",t.ask2(1,x,y,z)+1);
		}
		else if(op==2)
		{
			scanf("%d %d %d",&x,&y,&z);
			int l=0,r=INF,ans=-1;
			while(l<=r)
			{
				int mid=l+r>>1,v=t.ask(1,x,y,mid);
				if(v<z) l=mid+1;
				else ans=mid,r=mid-1;
			}
			printf("%d\n",ans);
		}
		else if(op==3)
		{
			scanf("%d %d",&x,&y);
			t.change(1,x,y);
			a[x]=y;
		}
		else if(op==4)
		{
			scanf("%d %d %d",&x,&y,&z);
			printf("%d\n",t.lst(1,x,y,z));
		}
		else if(op==5)
		{
			scanf("%d %d %d",&x,&y,&z);
			printf("%d\n",t.nxt(1,x,y,z));
		}
	}
	return 0;
}