#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, q, a[maxn], ans[maxn], val[maxn];
void Add(int x) {
	for(; x <= n; x += x & -x)
		++ val[x];
}
int Ask(int x) {
	int res = 0;
	for(; x; x -= x & -x)
		res += val[x];
	return res;
}
int cntodd, cnti;
void Mod(int x, int d) {
	if(ans[a[x]] & 1)
		cntodd += d;
	if(x == a[x])
		cnti += d;
}
int sum[maxn << 6], lc[maxn << 6], rc[maxn << 6], rt[maxn], tot;
void Upd(int &o, int l, int r, int p, int d) {
	if(!o)
		o = ++ tot;
	sum[o] += d;
	if(l == r)
		return;
	int mid = (l + r) >> 1;
	if(p <= mid)
		Upd(lc[o], l, mid, p, d);
	else
		Upd(rc[o], mid + 1, r, p, d);
}
int Que(int o, int l, int r, int ql, int qr) {
	if(!o)
		return 0;
	if(ql <= l && r <= qr)
		return sum[o];
	int mid = (l + r) >> 1, ans = 0;
	if(ql <= mid)
		ans += Que(lc[o], l, mid, ql, qr);
	if(qr > mid)
		ans += Que(rc[o], mid + 1, r, ql, qr);
	return ans;
}
void Update(int x, int v, int d) {
	for(; x <= n; x += x & -x)
		Upd(rt[x], 1, n, v, d);
}
int Query(int x, int l, int r) {
	int ans = 0;
	for(; x; x -= x & -x)
		ans += Que(rt[x], 1, n, l, r);
	return ans;
}
int main() {
	scanf("%d%d", &n, &q);
	long long all = 0;
	for(int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
		int w = Ask(n) - Ask(a[i]);
		all += w;
		ans[a[i]] += w;
		Add(a[i]);
	}
	memset(val, 0, sizeof val);
	for(int i = n; i; -- i) {
		ans[a[i]] += Ask(a[i]);
		Add(a[i]);
	}
	for(int i = 1; i <= n; ++ i)
		Mod(i, 1), Update(i, a[i], 1);
	for(int u, v; q --; ) {
		scanf("%d%d", &u, &v);
		Mod(u, -1), Mod(v, -1);
		Update(u, a[u], -1), Update(v, a[v], -1);
		swap(a[u], a[v]);
		Update(u, a[u], 1), Update(v, a[v], 1);
		// ans[a[u]] ^= 1, ans[a[v]] ^= 1;
		ans[a[u]] = a[u] - 1 - Query(u, 1, a[u] - 1) + Query(u, a[u] + 1, n), ans[a[v]] = a[v] - 1 - Query(v, 1, a[v] - 1) + Query(v, a[v] + 1, n);
// cerr << ans[a[u]] << " " << ans[a[v]] << endl;
		Mod(u, 1), Mod(v, 1);
		all ^= 1;
// cerr << all << " " << cnti << " " << cntodd << endl;
// for(int i = 1; i <= n; ++ i)
// 	cerr << a[i] << " ";
// cerr << endl;
// for(int i = 1; i <= n; ++ i)
// 	cerr << ans[i] << " ";
// cerr << endl;
		if(cnti == n) {
			puts("-1");
		}
		else if(all & 1) {
			printf("%d\n", n);
		}
		else if(cntodd) {
			printf("%d\n", n - 1);
		}
		else {
			printf("%d\n", n - 2);
		}
	}
}