#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+10;
ll n,q,op,x,v,a[N],t[N<<2],lazy[N<<2];
void up(ll rt){
	if(!lazy[rt]) t[rt]=max(t[rt<<1],t[rt<<1|1]);
	else t[rt]=0;
}
void build(ll rt,ll l,ll r){
	t[rt]=r;
	if(l==r) return;
	ll mid=l+r>>1;
	build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
}
void update(ll rt,ll l,ll r,ll rl,ll rr,ll k){
	if(rl>r||rr<l) return;
	if(l==r){t[rt]=(!(lazy[rt]+=k))*l;return;}
	if(rl<=l&&r<=rr){lazy[rt]+=k;up(rt);return;	}
	ll mid=l+r>>1;
	update(rt<<1,l,mid,rl,rr,k),update(rt<<1|1,mid+1,r,rl,rr,k);
	up(rt);
}
ll query(ll rt,ll l,ll r,ll rl,ll rr){
	if(rl>r||rr<l) return 0;
	if(rl<=l&&r<=rr) return t[rt];
	ll mid=l+r>>1;
	return max(query(rt<<1,l,mid,rl,rr),query(rt<<1|1,mid+1,r,rl,rr));
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;build(1,1,n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]<i) update(1,1,n,a[i]+1,i,1);
	}
	while(q--){
		cin>>op>>x;
		if(op==2) cout<<query(1,1,n,1,x)<<"\n";
		else{
			cin>>v;
			if(a[x]<x) update(1,1,n,a[x]+1,x,-1);
			a[x]=v;
			if(a[x]<x) update(1,1,n,a[x]+1,x,1);
		}
	}
	return 0;
}