#include<bits/stdc++.h>
#define fir first
#define sec second
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
template<typename type>
inline void chmin(type &x,const type &y)
{
	if(y<x)
		x=y;
}
template<typename type>
inline void chmax(type &x,const type &y)
{
	if(x<y)
		x=y;
}
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x)
{
	x=0;
	bool f=false;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')
		x=x*10+(ch^48),ch=getchar();
	if(f)
		x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y)
{
	read(x),read(y...);
}
constexpr int Max=1e6+10,inf=1e9;
struct heap
{
	priority_queue<int,vector<int>,greater<int>>p,q;
	inline void insert(const int &x)
	{
		p.push(x);
	}
	inline void erase(const int &x)
	{
		q.push(x);
	}
	inline void update()
	{
		while(!p.empty()&&!q.empty()&&p.top()==q.top())
			p.pop(),q.pop();
	}
	inline bool empty()
	{
		update();
		return p.empty();
	}
	inline int top()
	{
		update();
		return p.top();
	}
	inline void clear()
	{
		while(!p.empty())
			p.pop();
		while(!q.empty())
			q.pop();
	}
};
heap pos[Max];
int n,m,a[Max],pre[Max];
int bit[Max];
inline void add(int i,const int &k)
{
	for(;i<=n;i+=i&-i)
		bit[i]+=k;
}
inline int ask(int i)
{
	int ans=0;
	for(;i;i&=i-1)
		ans+=bit[i];
	return ans;
}
inline int kth(int k)
{
	if(!k)
		return 0;
	int i=0,s=0;
	for(int w=__lg(n);~w;--w)
	{
		int j=i+(1<<w);
		if(j<=n&&s+bit[j]<k)
			s+=bit[j],i=j;
	}
	return i+1;
}
bool in[Max];
struct segment_tree
{
	#define ls(p) ((p)<<1)
	#define rs(p) ((p)<<1|1)
	static constexpr int Size=(1<<21)+10;
	int sum[Size],tag[Size];
	inline void push_up(int p)
	{
		sum[p]=min(sum[ls(p)],sum[rs(p)]);
	}
	inline void set_tag(int p,const int &k)
	{
		sum[p]+=k,tag[p]+=k;
	}
	inline void push_down(int p)
	{
		if(tag[p])
		{
			set_tag(ls(p),tag[p]);
			set_tag(rs(p),tag[p]);
			tag[p]=0;
		}
	}
	int find(const int &ql,const int &qr,int p,int l,int r)
	{
		if(l>=ql&&r<=qr&&sum[p])
		{
			set_tag(p,-1);
			return 0;
		}
		if(l==r)
			return l;
		push_down(p);
		int mid=(l+r)>>1;
		int ans=0;
		if(ql<=mid)
			ans=find(ql,qr,ls(p),l,mid);
		if(ans)
			return ans;
		if(qr>=mid+1)
			ans=find(ql,qr,rs(p),mid+1,r);
		return ans;
	}
	void update(const int &ql,const int &qr,int p,int l,int r,const int &k)
	{
		if(l>=ql&&r<=qr)
		{
			set_tag(p,k);
			return;
		}
		push_down(p);
		int mid=(l+r)>>1;
		if(ql<=mid)
			update(ql,qr,ls(p),l,mid,k);
		if(qr>=mid+1)
			update(ql,qr,rs(p),mid+1,r,k);
		push_up(p);
	}
	void modify(const int &x,int p,int l,int r,const int &k)
	{
		if(l==r)
		{
			sum[p]=k;
			return;
		}
		push_down(p);
		int mid=(l+r)>>1;
		if(x<=mid)
			modify(x,ls(p),l,mid,k);
		else
			modify(x,rs(p),mid+1,r,k);
		push_up(p);
	}
	void build(int p,int l,int r)
	{
		tag[p]=0;
		if(l==r)
		{
			sum[p]=inf;
			return;
		}
		int mid=(l+r)>>1;
		build(ls(p),l,mid);
		build(rs(p),mid+1,r);
		push_up(p);
	}
	#undef ls
	#undef rs
}f,g;
int X,Y;
ll Sum=0;
inline void insert_check(int x)
{
	int k=a[x];
	if(pos[k].top()!=x)
		return;
	int u=kth(pre[x]);
	if(u<k)
	{
		if(!in[k])
		{
			if(k<n)
			{
				int i=f.find(k+1,n,1,1,n);
				if(i)
				{
					f.modify(i,1,1,n,inf);
					g.modify(i,1,1,n,0);
					add(i,1);
					in[i]=false;
					++X;
				}
				else
					i=n+1;
				if(i<=n)
					Sum+=i-k;	
				if(k+1<i)
					g.update(k+1,i-1,1,1,n,1);
			}
			add(k,-1);
			in[k]=true;
		}
		f.modify(k,1,1,n,ask(k)-pre[x]);
		g.modify(k,1,1,n,inf);
	}
	else
	{
		g.modify(k,1,1,n,pre[x]-ask(k));
		f.modify(k,1,1,n,inf);
	}
}
inline void insert(int x,int k)
{
	a[x]=k;
	if(!~k)
		return;
	pos[k].insert(x);
	insert_check(x);
}
inline void erase(int x)
{
	int k=a[x];
	if(!~k)
		return;
	pos[k].erase(x);
	if(!pos[k].empty()&&pos[k].top()<x)
		return;
	if(in[k])
	{
		if(k<n)
		{
			int i=g.find(k+1,n,1,1,n);
			if(i)
			{
				f.modify(i,1,1,n,0);
				g.modify(i,1,1,n,inf);
				add(i,-1);
				in[i]=true;
				++Y;
			}
			else
				i=n+1;
			if(i<=n)
				Sum+=i-k;
			if(k+1<i)
				f.update(k+1,i-1,1,1,n,1);
		}
		in[k]=false;
		add(k,1);
	}
	f.modify(k,1,1,n,inf);
	g.modify(k,1,1,n,inf);
	if(!pos[k].empty())
		insert_check(pos[k].top());
}
void solve()
{
	read(n,m);
	for(int i=1;i<=n;++i)
		read(a[i]),pre[i]=pre[i-1]+!a[i];
	fill(bit+1,bit+n+1,0);
	for(int i=1;i<=n;++i)
		pos[i].clear();
	fill(in+1,in+n+1,false);
	f.build(1,1,n);
	g.build(1,1,n);
	for(int i=1;i<=n;++i)
		add(i,1);
	int x,k,y;
	while(m--)
	{
		read(x,k,y);
		erase(x);
		insert(x,k);
		if(a[y])
			cout<<a[y]<<"\n";
		else
			cout<<kth(pre[y])<<"\n";
	}
	cerr<<X<<" "<<Y<<" "<<Sum<<"\n";
	X=Y=0;
	Sum=0;
}
signed main()
{
	// freopen("mex.in","r",stdin),freopen("std.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	int t=1;
	// read(t);
	while(t--)
		solve();
	cerr<<"times : "<<(db)clock()/CLOCKS_PER_SEC<<"\n";
	return 0;
}