#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second 
#define deb(var) cerr << #var << '=' << (var) << "; "
#define int long long
int n, q, a[200010];
int cnt[2];
int w[200010];
void add(int p, int x) {
	for (int i = p; i <= n; i += i & (-i)) w[i] += x;
}
int qry(int p) {
	int res = 0;
	for (int i = p; i; i -= i & (-i)) res += w[i];
	return res;
}
int rev = 0, flg = 0;
void rem(int p) {
	flg -= a[p] == p;
	cnt[(a[p] + 10000000 - p) & 1]--; 
}
void upd(int p) {
	flg += a[p] == p;
	cnt[(a[p] + 10000000 - p) & 1]++; 
}
signed main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		flg += a[i] == i;
		cnt[(a[i] + 10000000 - i) & 1]++;
		rev += qry(n) - qry(a[i]); add(a[i], 1);
	}
	rev &= 1;
	while (q--) {
		int u, v;
		cin >> u >> v;
		rem(u); rem(v);
		swap(a[u], a[v]);
		upd(u); upd(v);
		rev ^= 1;
		if (rev) {
			cout << n << "\n";
		} else {
			if (cnt[1]) {
				cout << n - 1 << "\n";
			} else {
				if (flg == n) cout << "-1\n";
				else {
					cout << n - 2 << "\n";
				}
			}
		}
	}
}