#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define pre(i, a, b) for(int i = (a); i >= (b); i--)
#define Ede(i, u) for(int i = h[u]; i; i = ne[i])
#define go(i, a) for(auto i : a)
//#define int long long
#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>
#define PIL pair<int, long long>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define mp make_pair
#define eb emplace_back
#define opb pop_back
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sf scanf
#define prf printf
#define el putchar('\n')
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define mmc(arr1, arr2) memcpy(arr1, arr2, sizeof(arr2))
const int inf = 0x3f3f3f3f;

template <typename T> inline void rd(T &x){
	x = 0; bool f = true; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = false; ch = getchar();}
	while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
	if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}

using namespace std;

const int N = 1e5 + 10;
int n, m, siz;
int a[N], H[N << 1], h;
struct Qu{
	int l, r;
	int pre, id;
}qu[N]; int qcnt;
bool cmp(Qu a, Qu b){
	if(a.l / siz != b.l / siz) return a.l < b.l;
	if(a.r / siz != b.r / siz) return a.r < b.r;
	return a.pre < b.pre;
}
int T; //这是实时pre 
struct M{
	int p, x, y; //x为？
}ops[N]; int mcnt; //被T代替了 
int cnt[N << 1], tot[N], ans[N];
void Add(int x){
	tot[cnt[x]]--;
	cnt[x]++;
	tot[cnt[x]]++;
}
void Del(int x){
	tot[cnt[x]]--;
	cnt[x]--;
	tot[cnt[x]]++;
}
void modify(int p, int x, int l, int r){
	if(l <= p && p <= r){
		Del(a[p]);
		Add(x);
	}
	a[p] = x;
}
int query(){
	for(int i = 1; ; i++){
		if(!tot[i]) return i;
	}
}

int main(){
	/*
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
	*/
	rd(n, m);
	siz = (int)pow(n, 2.0 / 3);
	rep(i, 1, n) rd(a[i]), H[++h] = a[i];
	rep(i, 1, m){
		int ins; rd(ins);
		if(ins == 1){
			++qcnt;
			rd(qu[qcnt].l, qu[qcnt].r);
			qu[qcnt].pre = T, qu[qcnt].id = qcnt;
		}else{
			T++;
			rd(ops[T].p, ops[T].y);
			H[++h] = ops[T].y;
		}
	}
	sort(H + 1, H + h + 1);
	int len = unique(H + 1, H + h + 1) - (H + 1);
	//开始赋值
	rep(i, 1, n) a[i] = lower_bound(H + 1, H + len + 1, a[i]) - H; //从1开始 
	rep(i, 1, n) ops[i].y = lower_bound(H + 1, H + len + 1, ops[i].y) - H;
	//直接开始交换 
	rep(i, 1, T) ops[i].x = a[ops[i].p]/*未交换的值*/, a[ops[i].p] = ops[i].y;
	sort(qu + 1, qu + qcnt + 1, cmp);
	
	int tm = T; //时间戳 
	for(int i = 1, l = qu[1].l, r = qu[1].l - 1; i <= qcnt; i++){
		//?顺序
		while(l < qu[i].l) Del(l++);
		while(r > qu[i].r) Del(r--);
		while(l > qu[i].l) Add(--l);
		while(r < qu[i].r) Add(++r);
		while(tm < qu[i].pre) tm++, modify(ops[tm].p, ops[tm].y, l, r);
		while(tm > qu[i].pre) modify(ops[tm].p, ops[tm].x, l, r), tm--;
		ans[qu[i].id] = query(); 
	}
	rep(i, 1, qcnt) prf("%d\n", ans[i]);
	return 0;
}