```go
package main

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

const MAX = 200040

var (
	bit [MAX]int
	seg [4 * MAX]int
)

func update(node, l, r, idx, val int) {
	if l == r {
		seg[node] = val
		return
	}
	mid := (l + r) >> 1
	if idx <= mid {
		update(node<<1, l, mid, idx, val)
	} else {
		update(node<<1|1, mid+1, r, idx, val)
	}
	seg[node] = seg[node<<1] + seg[node<<1|1]
}

func queryMax(node, l, r int) int {
	if seg[node] == 0 {
		return -1
	}
	if l == r {
		return l
	}
	mid := (l + r) >> 1
	if seg[node<<1|1] > 0 {
		return queryMax(node<<1|1, mid+1, r)
	}
	return queryMax(node<<1, l, mid)
}

func add(x int) {
	i := x
	for bit[i] == 1 {
		bit[i] = 0
		update(1, 0, MAX-1, i, 0)
		i++
	}
	bit[i] = 1
	update(1, 0, MAX-1, i, 1)
}

func remove(x int) {
	i := x
	for bit[i] == 0 {
		bit[i] = 1
		update(1, 0, MAX-1, i, 1)
		i++
	}
	bit[i] = 0
	update(1, 0, MAX-1, i, 0)
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, q int
	fmt.Fscan(reader, &n, &q)

	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &a[i])
		add(a[i])
	}

	for i := 0; i < q; i++ {
		var k, l int
		fmt.Fscan(reader, &k, &l)
		k--
		remove(a[k])
		add(l)
		a[k] = l
		fmt.Fprintln(writer, queryMax(1, 0, MAX-1))
	}
}
```