For problem statement at 0-999/900-999/940-949/940/problemF.txt this is a correct solution, but verifier at 0-999/900-999/940-949/940/verifierF.go ends with case 5 failed: expected 3
2
2
3
3 got 3
2
2
3
1
exit status 1 can you fix the verifier? package main

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

type FastScanner struct {
	r *bufio.Reader
}

func NewFastScanner() *FastScanner {
	return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}

func (fs *FastScanner) NextInt() int {
	sign := 1
	val := 0
	b, _ := fs.r.ReadByte()
	for (b < '0' || b > '9') && b != '-' {
		b, _ = fs.r.ReadByte()
	}
	if b == '-' {
		sign = -1
		b, _ = fs.r.ReadByte()
	}
	for b >= '0' && b <= '9' {
		val = val*10 + int(b-'0')
		b, _ = fs.r.ReadByte()
	}
	return val * sign
}

type Query struct {
	l, r, t, id int
}
type Mod struct {
	pos, old, new int
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	n := in.NextInt()
	q := in.NextInt()

	rawA := make([]int, n)
	vals := make([]int, 0, n+q+5)
	for i := 0; i < n; i++ {
		rawA[i] = in.NextInt()
		vals = append(vals, rawA[i])
	}

	rawCur := make([]int, n)
	copy(rawCur, rawA)

	rawMods := make([]Mod, 0, q)
	queries := make([]Query, 0, q)
	ansIdx := 0
	for i := 0; i < q; i++ {
		t := in.NextInt()
		if t == 1 {
			l := in.NextInt() - 1
			r := in.NextInt() - 1
			queries = append(queries, Query{l: l, r: r, t: len(rawMods), id: ansIdx})
			ansIdx++
		} else {
			p := in.NextInt() - 1
			x := in.NextInt()
			rawMods = append(rawMods, Mod{pos: p, old: rawCur[p], new: x})
			rawCur[p] = x
			vals = append(vals, x)
		}
	}

	sort.Slice(vals, func(i, j int) bool { return vals[i] < vals[j] })
	uniq := make([]int, 0, len(vals))
	for i, v := range vals {
		if i == 0 || v != vals[i-1] {
			uniq = append(uniq, v)
		}
	}
	comp := func(x int) int {
		i := sort.SearchInts(uniq, x)
		return i
	}

	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = comp(rawA[i])
	}
	mods := make([]Mod, len(rawMods))
	for i, m := range rawMods {
		mods[i] = Mod{pos: m.pos, old: comp(m.old), new: comp(m.new)}
	}

	BLOCK := int(math.Pow(float64(n), 2.0/3.0)) + 1
	sort.Slice(queries, func(i, j int) bool {
		ai, aj := queries[i], queries[j]
		bl1 := ai.l / BLOCK
		bl2 := aj.l / BLOCK
		if bl1 != bl2 {
			return bl1 < bl2
		}
		br1 := ai.r / BLOCK
		br2 := aj.r / BLOCK
		if br1 != br2 {
			return br1 < br2
		}
		return ai.t < aj.t
	})

	M := len(uniq)
	freqVal := make([]int, M)
	cur := make([]int, n)
	copy(cur, a)

	sizeC := n + 2
	cntCount := make([]int, sizeC)
	bsz := int(math.Sqrt(float64(sizeC))) + 1
	numBlocks := (sizeC + bsz - 1) / bsz
	blocks := make([]int, numBlocks)
	for c := 1; c < sizeC; c++ {
		blocks[c/bsz]++
	}

	updateCC := func(c, delta int) {
		if c <= 0 {
			return
		}
		bi := c / bsz
		beforeZero := cntCount[c] == 0
		cntCount[c] += delta
		afterZero := cntCount[c] == 0
		if beforeZero && !afterZero {
			blocks[bi]--
		} else if !beforeZero && afterZero {
			blocks[bi]++
		}
	}

	addIdx := func(idx int) {
		v := cur[idx]
		f := freqVal[v]
		if f >= 1 {
			updateCC(f, -1)
		}
		f++
		freqVal[v] = f
		updateCC(f, +1)
	}
	remIdx := func(idx int) {
		v := cur[idx]
		f := freqVal[v]
		updateCC(f, -1)
		f--
		freqVal[v] = f
		if f >= 1 {
			updateCC(f, +1)
		}
	}
	applyMod := func(k int, L, R int) {
		m := mods[k]
		p := m.pos
		if L <= p && p <= R {
			remIdx(p)
			cur[p] = m.new
			addIdx(p)
		} else {
			cur[p] = m.new
		}
	}
	unapplyMod := func(k int, L, R int) {
		m := mods[k]
		p := m.pos
		if L <= p && p <= R {
			remIdx(p)
			cur[p] = m.old
			addIdx(p)
		} else {
			cur[p] = m.old
		}
	}
	getMex := func() int {
		for b := 0; b < numBlocks; b++ {
			if blocks[b] > 0 {
				start := b * bsz
				if start == 0 {
					start = 1
				}
				end := start + bsz - 1
				if end >= sizeC {
					end = sizeC - 1
				}
				for i := start; i <= end; i++ {
					if cntCount[i] == 0 {
						return i
					}
				}
			}
		}
		return sizeC - 1
	}

	curL, curR, curT := 0, -1, 0
	ans := make([]int, len(queries))
	for _, qu := range queries {
		for curT < qu.t {
			applyMod(curT, curL, curR)
			curT++
		}
		for curT > qu.t {
			curT--
			unapplyMod(curT, curL, curR)
		}
		for curL > qu.l {
			curL--
			addIdx(curL)
		}
		for curR < qu.r {
			curR++
			addIdx(curR)
		}
		for curL < qu.l {
			remIdx(curL)
			curL++
		}
		for curR > qu.r {
			remIdx(curR)
			curR--
		}
		ans[qu.id] = getMex()
	}

	for i := 0; i < len(ans); i++ {
		fmt.Fprintln(out, ans[i])
	}
}