#include <bits/stdc++.h>
using namespace std;

const int maxn=200000;

int tr[maxn+50];
inline int lowbit(int x){return x&(-x);}
void add(int pos,int val){
	for (int i=pos;i<=maxn;i+=lowbit(i)) tr[i]+=val;
}
int query(int pos){
	int ans=0;
	for (int i=pos;i>=1;i-=lowbit(i)) ans+=tr[i];
	return ans;
}

int n,Q;
int a[maxn+50];
int ok[maxn+50],okcnt;
int odd[maxn+50],oddcnt;

int tot;

int main(){
	ios_base::sync_with_stdio(false);
	cin >> n >> Q;
	for (int i=1;i<=n;i++) cin >> a[i];
	
	for (int i=1;i<=n;i++){
		if (a[i]==i) ok[i]=1;
		okcnt+=ok[i];
	}
	for (int i=1;i<=n;i++){
		odd[i]=(a[i]+i)%2;
		oddcnt+=odd[i];
	}
	for (int i=1;i<=n;i++){
		tot^=(i-1-query(a[i]))%2;
		add(a[i],1);
	}
	
	for (;Q--;){
		int x,y;
		cin >> x >> y;
		if (x>y) swap(x,y);
		
		okcnt-=ok[x];
		okcnt-=ok[y];
		swap(a[x],a[y]);
		ok[x]=(a[x]==x);
		ok[y]=(a[y]==y);
		okcnt+=ok[x];
		okcnt+=ok[y];
		
		tot^=1;
		swap(odd[x],odd[y]);
		if ((y-x)%2==1){
			oddcnt-=odd[x];
			oddcnt-=odd[y];
			odd[x]^=1;
			odd[y]^=1;
			oddcnt+=odd[x];
			oddcnt+=odd[y];
		}
		/*
		cerr << "-----------------" << endl;
		for (int i=1;i<=n;i++) cerr << a[i] << " ";
		cerr << endl;
		for (int i=1;i<=n;i++) cerr << odd[i] << " ";
		cerr << endl;
		for (int i=1;i<=n;i++) cerr << ok[i] << " ";
		cerr << endl;
		cerr << "okcnt,oddcnt,tot : " << okcnt << " " << oddcnt << " " << tot << endl;
		*/
		if (okcnt==n){
			cout << -1 << "\n";
		}
		else if (tot%2==1){
			cout << n << "\n";
		}
		else if (oddcnt>=1){
			cout << n-1 << "\n";
		}
		else{
			cout << n-2 << "\n";
		}
	}
	return 0;
}