#include<bits/stdc++.h>
using namespace std;
#define RI register int
inline int read() {
    RI x=0, w=0;register char ch=0;
    while(!isdigit(ch)) w|=ch=='-', ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    return w?-x:x;
}
const int MAXN=2e5+1;
int N, Q, a[MAXN], tree[MAXN];
inline int lowbit(int x) { return x&-x; }
inline void upd(int i) { for(;i<=N;i+=lowbit(i)) tree[i]++; }
inline int ask(int i) { int ans=0; for(;i;i-=lowbit(i)) ans+=tree[i]; return ans; }  
signed main() {
//	freopen("a.in","r",stdin);
	N=read(), Q=read(); int tot1=0, tot2=0, x, y; bool flag=0;
	for(RI i=1;i<=N;i++) a[i]=read(), tot1+=a[i]==i, tot2+=(a[i]+i)&1;
	for(RI i=1;i<=N;i++) {
		flag^=ask(a[i])&1;
		upd(a[i]);	
	} 
	for(RI i=1;i<=Q;i++) {
		x=read(), y=read(); swap(a[x],a[y]);
		tot1+=(a[y]==y)+(a[x]==x)-(a[y]==x)-(a[x]==y);
		tot2+=((a[y]+y)&1)+((a[x]+x)&1)-((a[x]+y)&1)-((a[y]+x)&1);
		if(flag^(i&1)) printf("%d\n",N);
		else {
			if(tot1==N) printf("%d\n",-1); 
			else if(tot2) printf("%d\n",N-1);
			else printf("%d\n",N-2);
		}
	}
    return 0; 
}