package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	var n, q int
	fmt.Fscan(in, &n, &q)
	a := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Fscan(in, &a[i])
	}
	type Query struct {
		ty, l, r int
	}
	queries := make([]Query, q)
	allvals := make(map[int]bool)
	for i := 0; i < q; i++ {
		var ty, l, r int
		fmt.Fscan(in, &ty, &l, &r)
		queries[i] = Query{ty, l, r}
		if ty == 2 {
			allvals[r] = true
		}
	}
	for i := 1; i <= n; i++ {
		allvals[a[i]] = true
	}
	var sortedVals []int
	for v := range allvals {
		sortedVals = append(sortedVals, v)
	}
	sort.Ints(sortedVals)
	D := len(sortedVals)
	val2id := make(map[int]int)
	for i := 0; i < D; i++ {
		val2id[sortedVals[i]] = i + 1
	}
	type Up struct {
		p, x, prev int
	}
	updates := make([]Up, 0)
	sim_a := make([]int, n+1)
	copy(sim_a, a)
	for i := 0; i < q; i++ {
		if queries[i].ty == 2 {
			p := queries[i].l
			x := queries[i].r
			prev := sim_a[p]
			updates = append(updates, Up{p, x, prev})
			sim_a[p] = x
		}
	}
	type MoQ struct {
		l, r, t, index int
	}
	var mo []MoQ
	current_up := 0
	var ansCnt int
	for i := 0; i < q; i++ {
		if queries[i].ty == 1 {
			mo = append(mo, MoQ{queries[i].l, queries[i].r, current_up, ansCnt})
			ansCnt++
		} else {
			current_up++
		}
	}
	mm := len(mo)
	const BLOCK = 2150
	sort.Slice(mo, func(i, j int) bool {
		bi := mo[i].l / BLOCK
		bj := mo[j].l / BLOCK
		if bi != bj {
			return bi < bj
		}
		ti := mo[i].t / BLOCK
		tj := mo[j].t / BLOCK
		if ti != tj {
			return ti < tj
		}
		return mo[i].r < mo[j].r
	})
	maxN := n + 2
	tree := make([]int, 4*maxN)
	inf := n + 3
	var build func(int, int, int)
	build = func(node, start, end int) {
		if start == end {
			tree[node] = start
			return
		}
		mid := (start + end) / 2
		build(2*node, start, mid)
		build(2*node+1, mid+1, end)
		if tree[2*node] < tree[2*node+1] {
			tree[node] = tree[2*node]
		} else {
			tree[node] = tree[2*node+1]
		}
	}
	build(1, 1, maxN)
	var updateTree func(int, int, int, int, int)
	updateTree = func(node, start, end, idx, val int) {
		if start == end {
			tree[node] = val
			return
		}
		mid := (start + end) / 2
		if idx <= mid {
			updateTree(2*node, start, mid, idx, val)
		} else {
			updateTree(2*node+1, mid+1, end, idx, val)
		}
		if tree[2*node] < tree[2*node+1] {
			tree[node] = tree[2*node]
		} else {
			tree[node] = tree[2*node+1]
		}
	}
	val_freq := make([]int, D+1)
	meta := make([]int, n+2)
	current_a := make([]int, n+1)
	copy(current_a, a)
	current_l := 1
	current_r := 0
	current_t := 0
	answers := make([]int, ansCnt)
	var update_freq func(int, int)
	update_freq = func(vid, delta int) {
		old_c := val_freq[vid]
		val_freq[vid] += delta
		new_c := val_freq[vid]
		meta[old_c]--
		if meta[old_c] == 0 && old_c >= 1 {
			updateTree(1, 1, maxN, old_c, old_c)
		}
		meta[new_c]++
		if meta[new_c] == 1 && new_c >= 1 {
			updateTree(1, 1, maxN, new_c, inf)
		}
	}
	var add func(int)
	add = func(pos int) {
		vid := val2id[current_a[pos]]
		update_freq(vid, 1)
	}
	var remove func(int)
	remove = func(pos int) {
		vid := val2id[current_a[pos]]
		update_freq(vid, -1)
	}
	for i := 0; i < mm; i++ {
		qdel := mo[i]
		for current_t < qdel.t {
			current_t++
			u := updates[current_t-1]
			p := u.p
			x := u.x
			prev := u.prev
			current_a[p] = x
			if p >= current_l && p <= current_r {
				update_freq(val2id[prev], -1)
				update_freq(val2id[x], 1)
			}
		}
		for current_t > qdel.t {
			u := updates[current_t-1]
			p := u.p
			x := u.x
			old := u.prev
			current_a[p] = old
			if p >= current_l && p <= current_r {
				update_freq(val2id[x], -1)
				update_freq(val2id[old], 1)
			}
			current_t--
		}
		for current_r < qdel.r {
			current_r++
			add(current_r)
		}
		for current_r > qdel.r {
			remove(current_r)
			current_r--
		}
		for current_l > qdel.l {
			current_l--
			add(current_l)
		}
		for current_l < qdel.l {
			remove(current_l)
			current_l++
		}
		answers[qdel.index] = tree[1]
	}
	out := bufio.NewWriter(os.Stdout)
	for i := 0; i < ansCnt; i++ {
		fmt.Fprintln(out, answers[i])
	}
	out.Flush()
}