package main

import (
	"io/ioutil"
	"os"
	"sort"
)

var buffer []byte
var pointer int

func scanInt() int {
	for pointer < len(buffer) && buffer[pointer] <= ' ' {
		pointer++
	}
	if pointer >= len(buffer) {
		return 0
	}
	res := 0
	for pointer < len(buffer) && buffer[pointer] > ' ' {
		res = res*10 + int(buffer[pointer]-'0')
		pointer++
	}
	return res
}

func main() {
	buffer, _ = ioutil.ReadAll(os.Stdin)

	n := scanInt()
	q := scanInt()
	if n == 0 {
		return
	}

	a := make([]int, n+1)
	vals := make([]int, 0, n+q)
	for i := 1; i <= n; i++ {
		a[i] = scanInt()
		vals = append(vals, a[i])
	}

	type Query struct {
		l, r, t, id, lBlock, rBlock int
	}
	type Update struct {
		p, old, new int
	}

	var queries []Query
	var updates []Update

	currentA := make([]int, n+1)
	copy(currentA, a)

	for i := 0; i < q; i++ {
		typ := scanInt()
		if typ == 1 {
			l := scanInt()
			r := scanInt()
			queries = append(queries, Query{
				l: l, r: r, t: len(updates), id: len(queries),
			})
		} else {
			p := scanInt()
			x := scanInt()
			updates = append(updates, Update{
				p: p, old: currentA[p], new: x,
			})
			currentA[p] = x
			vals = append(vals, x)
		}
	}

	sort.Ints(vals)
	unique := 0
	for i := 0; i < len(vals); i++ {
		if i == 0 || vals[i] != vals[i-1] {
			vals[unique] = vals[i]
			unique++
		}
	}
	vals = vals[:unique]

	getVal := func(x int) int {
		l, r := 0, unique-1
		for l <= r {
			m := l + (r-l)/2
			if vals[m] == x {
				return m + 1
			}
			if vals[m] < x {
				l = m + 1
			} else {
				r = m - 1
			}
		}
		return 0
	}

	for i := 1; i <= n; i++ {
		a[i] = getVal(a[i])
	}
	for i := range updates {
		updates[i].old = getVal(updates[i].old)
		updates[i].new = getVal(updates[i].new)
	}

	B := 2154
	for i := range queries {
		queries[i].lBlock = queries[i].l / B
		queries[i].rBlock = queries[i].r / B
	}

	sort.Slice(queries, func(i, j int) bool {
		if queries[i].lBlock != queries[j].lBlock {
			return queries[i].lBlock < queries[j].lBlock
		}
		if queries[i].rBlock != queries[j].rBlock {
			if queries[i].lBlock%2 == 0 {
				return queries[i].rBlock < queries[j].rBlock
			}
			return queries[i].rBlock > queries[j].rBlock
		}
		if queries[i].rBlock%2 == 0 {
			return queries[i].t < queries[j].t
		}
		return queries[i].t > queries[j].t
	})

	ans := make([]int, len(queries))
	count := make([]int, unique+1)
	freqCount := make([]int, n+2)

	add := func(x int) {
		f := count[x]
		if f > 0 {
			freqCount[f]--
		}
		count[x]++
		freqCount[count[x]]++
	}

	remove := func(x int) {
		f := count[x]
		freqCount[f]--
		count[x]--
		if count[x] > 0 {
			freqCount[count[x]]++
		}
	}

	applyUpdate := func(u Update, l, r int, reverse bool) {
		p := u.p
		var from, to int
		if reverse {
			from, to = u.new, u.old
		} else {
			from, to = u.old, u.new
		}
		if p >= l && p <= r {
			remove(from)
			add(to)
		}
		a[p] = to
	}

	L, R, T := 1, 0, 0

	for _, q := range queries {
		for T < q.t {
			applyUpdate(updates[T], L, R, false)
			T++
		}
		for T > q.t {
			T--
			applyUpdate(updates[T], L, R, true)
		}
		for L > q.l {
			L--
			add(a[L])
		}
		for R < q.r {
			R++
			add(a[R])
		}
		for L < q.l {
			remove(a[L])
			L++
		}
		for R > q.r {
			remove(a[R])
			R--
		}

		res := 1
		for freqCount[res] > 0 {
			res++
		}
		ans[q.id] = res
	}

	out := make([]byte, 0, len(ans)*10)
	for _, v := range ans {
		if v == 0 {
			out = append(out, '0', '\n')
			continue
		}
		var tmp [20]byte
		idx := 20
		for v > 0 {
			idx--
			tmp[idx] = byte(v%10) + '0'
			v /= 10
		}
		out = append(out, tmp[idx:]...)
		out = append(out, '\n')
	}
	os.Stdout.Write(out)
}