```go
package main

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

var (
	a        []int
	cur_a    []int
	freq     []int
	freq_cnt []int
	updates  []Update
	queries  []Query
	L, R, T  int
	mex      int
)

type Update struct {
	pos, old, new int
}

type Query struct {
	l, r, t, idx int
}

func add(pos int) {
	v := cur_a[pos]
	f := freq[v]
	if f > 0 {
		freq_cnt[f]--
		if freq_cnt[f] == 0 && f < mex {
			mex = f
		}
	}
	freq[v]++
	freq_cnt[f+1]++
	if f+1 == mex {
		for freq_cnt[mex] > 0 {
			mex++
		}
	}
}

func remove(pos int) {
	v := cur_a[pos]
	f := freq[v]
	freq_cnt[f]--
	if freq_cnt[f] == 0 && f < mex {
		mex = f
	}
	freq[v]--
	if freq[v] > 0 {
		freq_cnt[freq[v]]++
		if freq[v] == mex {
			for freq_cnt[mex] > 0 {
				mex++
			}
		}
	}
}

func applyUpdate(idx int) {
	u := updates[idx]
	pos := u.pos
	if pos >= L && pos <= R {
		remove(pos)
	}
	cur_a[pos] = u.new
	if pos >= L && pos <= R {
		add(pos)
	}
}

func revertUpdate(idx int) {
	u := updates[idx]
	pos := u.pos
	if pos >= L && pos <= R {
		remove(pos)
	}
	cur_a[pos] = u.old
	if pos >= L && pos <= R {
		add(pos)
	}
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	readInt := func() int {
		sc.Scan()
		x, _ := strconv.Atoi(sc.Text())
		return x
	}

	n := readInt()
	q := readInt()

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

	rawQueries := make([]struct{ t, a1, a2 int }, q)
	for i := 0; i < q; i++ {
		rawQueries[i].t = readInt()
		rawQueries[i].a1 = readInt()
		rawQueries[i].a2 = readInt()
		if rawQueries[i].t == 2 {
			allVals = append(allVals, rawQueries[i].a2)
		}
	}

	sort.Ints(allVals)
	unique := allVals[:0]
	for _, v := range allVals {
		if len(unique) == 0 || unique[len(unique)-1] != v {
			unique = append(unique, v)
		}
	}
	comp := make(map[int]int, len(unique))
	for i, v := range unique {
		comp[v] = i + 1
	}
	M := len(unique)

	for i := 0; i < n; i++ {
		a[i] = comp[a[i]]
	}
	cur_a = make([]int, n)
	copy(cur_a, a)

	updates = make([]Update, 0, q)
	queries = make([]Query, 0, q)
	qIdx := 0
	temp := make([]int, n)
	copy(temp, a)

	for _, rq := range rawQueries {
		if rq.t == 1 {
			l := rq.a1 - 1
			r := rq.a2 - 1
			queries = append(queries, Query{l, r, len(updates), qIdx})
			qIdx++
		} else {
			pos := rq.a1 - 1
			x := comp[rq.a2]
			old := temp[pos]
			updates = append(updates, Update{pos, old, x})
			temp[pos] = x
		}
	}

	B := int(math.Pow(float64(n), 2.0/3.0))
	if B < 1 {
		B = 1
	}
	sort.Slice(queries, func(i, j int) bool {
		qi, qj := queries[i], queries[j]
		bi, bj := qi.l/B, qj.l/B
		if bi != bj {
			return bi < bj
		}
		ri, rj := qi.r/B, qj.r/B
		if ri != rj {
			if bi%2 == 0 {
				return ri < rj
			} else {
				return ri > rj
			}
		}
		if ri%2 == 0 {
			return qi.t < qj.t
		} else {
			return qi.t > qj.t
		}
	})

	freq = make([]int, M+1)
	freq_cnt = make([]int, n+2)
	ans := make([]int, qIdx)

	L = 0
	R = -1
	T = 0
	mex = 1

	for _, q := range queries {
		for T < q.t {
			applyUpdate(T)
			T++
		}
		for T > q.t {
			T--
			revertUpdate(T)
		}
		for L > q.l {
			L--
			add(L)
		}
		for R < q.r {
			R++
			add(R)
		}
		for L < q.l {
			remove(L)
			L++
		}
		for R > q.r {
			remove(R)
			R--
		}
		ans[q.idx] = mex
	}

	out := bufio.NewWriter(os.Stdout)
	for i := 0; i < qIdx; i++ {
		fmt.Fprintln(out, ans[i])
	}
	out.Flush()
}
```