package main

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

type SegmentTree struct {
	n    int
	tree []int
	lazy []int
}

func NewSegmentTree(n int) *SegmentTree {
	return &SegmentTree{
		n:    n,
		tree: make([]int, 4*n),
		lazy: make([]int, 4*n),
	}
}

func (st *SegmentTree) push(node int) {
	if st.lazy[node] != 0 {
		st.tree[2*node] += st.lazy[node]
		st.lazy[2*node] += st.lazy[node]
		st.tree[2*node+1] += st.lazy[node]
		st.lazy[2*node+1] += st.lazy[node]
		st.lazy[node] = 0
	}
}

func (st *SegmentTree) update(node, l, r, ql, qr, val int) {
	if ql > r || qr < l {
		return
	}
	if ql <= l && r <= qr {
		st.tree[node] += val
		st.lazy[node] += val
		return
	}
	st.push(node)
	mid := (l + r) / 2
	st.update(2*node, l, mid, ql, qr, val)
	st.update(2*node+1, mid+1, r, ql, qr, val)
	if st.tree[2*node] > st.tree[2*node+1] {
		st.tree[node] = st.tree[2*node]
	} else {
		st.tree[node] = st.tree[2*node+1]
	}
}

func (st *SegmentTree) query() int {
	node := 1
	l, r := 0, st.n-1
	for l != r {
		st.push(node)
		mid := (l + r) / 2
		if st.tree[2*node] >= st.tree[2*node+1] {
			node = 2 * node
			r = mid
		} else {
			node = 2*node + 1
			l = mid + 1
		}
	}
	return l
}

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

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

	length := 2*n + 1
	p := make([]int, length+1)
	pos := make([]int, length+1)

	st := NewSegmentTree(length)

	addInterval := func(u, v, val int) {
		if u <= v {
			st.update(1, 0, length-1, u, v, val)
		} else {
			st.update(1, 0, length-1, u, length-1, val)
			st.update(1, 0, length-1, 0, v, val)
		}
	}

	updateVal := func(i, val int) {
		if p[i] > i {
			addInterval(i, p[i]-1, val)
		} else if p[i] < i {
			addInterval(i, length-1, val)
			addInterval(0, p[i]-1, val)
		}
	}

	for i := 1; i <= length; i++ {
		fmt.Fscan(reader, &p[i])
		pos[p[i]] = i
	}

	for i := 1; i <= length; i++ {
		updateVal(i, 1)
	}

	for i := 0; i < q; i++ {
		var u, v int
		fmt.Fscan(reader, &u, &v)

		updateVal(u, -1)
		updateVal(v, -1)

		p[u], p[v] = p[v], p[u]
		pos[p[u]] = u
		pos[p[v]] = v

		updateVal(u, 1)
		updateVal(v, 1)

		maxVal := st.tree[1]
		if maxVal <= n {
			fmt.Fprintln(writer, st.query())
		} else {
			fmt.Fprintln(writer, -1)
		}
	}
}