#include<bits/stdc++.h>
using namespace std;
#define int long long
 
int lc(int x) { return x << 1; }
int rc(int x) { return x << 1 | 1; }
 
const int nr = 1e5 + 10;
int n, q, M, p[nr << 1], pre[nr << 1], pos[nr << 1];
int calc(int x) { return x == n + 1 ? 0 : x > n + 1 ? 1 : -1; }
 
struct segment1
{
	pair<int, int> seg[nr << 3];
	int tag[nr << 3];
	
	void pushup(int x)
	{
		seg[x] = min(seg[lc(x)], seg[rc(x)]);
	}
	
	void build(int x, int l, int r)
	{
		tag[x] = 0;
		if (l == r)
		{
			seg[x] = make_pair(pre[l], l);
			return;
		}
		int mid = l + r >> 1;
		build(lc(x), l, mid);
		build(rc(x), mid + 1, r);
		pushup(x);
	}
	
	void movetag(int x, int k)
	{
		seg[x].first += k;
		tag[x] += k;
	}
	
	void pushdown(int x)
	{
		if (tag[x])
		{
			movetag(lc(x), tag[x]);
			movetag(rc(x), tag[x]);
		}
		tag[x] = 0;
	}
	
	void upd(int x, int l, int r, int ql, int qr, int k)
	{
		if (ql <= l && r <= qr)
		{
			movetag(x, k);
			return;
		}
		pushdown(x);
		int mid = l + r >> 1;
		if (ql <= mid) upd(lc(x), l, mid, ql, qr, k);
		if (mid + 1 <= qr) upd(rc(x), mid + 1, r, ql, qr, k);
		pushup(x);
	}
	
	int query(int x, int l, int r, int q)
	{
		if (l == r) return seg[x].first;
		pushdown(x);
		int mid = l + r >> 1;
		if (q <= mid) return query(lc(x), l, mid, q);
		return query(rc(x), mid + 1, r, q);
	}
} tr1;
 
struct segment2
{
	int seg[nr << 3];
	
	void pushup(int x)
	{
		seg[x] = seg[lc(x)] + seg[rc(x)];
	}
	
	void build(int x, int l, int r)
	{
		if (l == r)
		{
			seg[x] = pos[l] > pos[l + 1];
			return;
		}
		int mid = l + r >> 1;
		build(lc(x), l, mid);
		build(rc(x), mid + 1, r);
		pushup(x);
	}
	
	void upd(int x, int l, int r, int q)
	{
		if (q < 1 || q > (n << 1)) return;
		if (l == r)
		{
			seg[x] = pos[l] > pos[l + 1];
			return;
		}
		int mid = l + r >> 1;
		if (q <= mid) upd(lc(x), l, mid, q);
		else upd(rc(x), mid + 1, r, q);
		pushup(x);
	}
	
	int query(int x, int l, int r, int ql, int qr)
	{
		if (ql <= l && r <= qr) return seg[x];
		int mid = l + r >> 1, res = 0;
		if (ql <= mid) res += query(lc(x), l, mid, ql, qr);
		if (mid + 1 <= qr) res += query(rc(x), mid + 1, r, ql, qr);
		return res;
	}
} tr2;
 
signed main()
{
//	freopen("hack.txt", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= (n << 1 | 1); i++)
		cin >> p[i], pos[p[i]] = i, pre[i] = pre[i - 1] + calc(p[i]); M = pos[n + 1];
	tr1.build(1, 1, n << 1 | 1);
	tr2.build(1, 1, n << 1);
	while (q--)
	{
		int x, y; cin >> x >> y; 
		tr1.upd(1, 1, n << 1 | 1, x, n << 1 | 1, calc(p[y]) - calc(p[x]));
		tr1.upd(1, 1, n << 1 | 1, y, n << 1 | 1, calc(p[x]) - calc(p[y]));
		swap(pos[p[x]], pos[p[y]]), swap(p[x], p[y]), M = pos[n + 1];
		tr2.upd(1, 1, n << 1, p[x] - 1), tr2.upd(1, 1, n << 1, p[x]);
		tr2.upd(1, 1, n << 1, p[y] - 1), tr2.upd(1, 1, n << 1, p[y]);
		pair<int, int> mn = tr1.seg[1];
		int pre = tr1.query(1, 1, n << 1 | 1, M), nowpre = max(pre - mn.first, pre);
		if (nowpre > 0) { cout << (mn.first < 0 ? mn.second % (n << 1 | 1) : 0) << '\n'; continue; }
		if (tr2.query(1, 1, n << 1, 1, n) - (pos[1] > M) > 0) { cout << M % (n << 1 | 1) << '\n'; continue; }
		if (tr2.query(1, 1, n << 1, n + 1, n << 1) - (pos[n << 1 | 1] < M) > 0) { cout << M - 1 << '\n'; continue; }
		cout << -1 << '\n';
	}
	return 0;
}