#include<bits/stdc++.h>
using namespace std;
int a[200001];
class FenwickTree{
	private:
		int tree[300001],sz=0;
		inline int lowbit(int x)
		{
			return x&(-x);
		}
	public:
		inline void init(int n)
		{
			memset(tree,0,sizeof(tree));
			sz=n;
		}
		inline void update(int pos,int val)
		{
			while(pos<=sz)
			{
				tree[pos]+=val;
				pos+=lowbit(pos);
			}
		}
		inline int query(int pos)
		{
			int sum=0;
			while(pos)
			{
				sum+=tree[pos];
				pos-=lowbit(pos);
			}
			return sum;
		}
};
FenwickTree F;
inline pair<int,int> Swap(int u,int v)
{
	int diff=0,odd=0;
	if(a[u]!=u) 
		diff--;
	if(a[v]!=v)
		diff--;
	if(abs(a[u]-u)&1)
		odd--;
	if(abs(a[v]-v)&1)
		odd--;
	swap(a[u],a[v]);
	if(a[u]!=u) 
		diff++;
	if(a[v]!=v)
		diff++;
	if(abs(a[u]-u)&1)
		odd++;
	if(abs(a[v]-v)&1)
		odd++;
	return make_pair(diff,odd);
}
int main(){
	int n,q;
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int diff=0,odd=0;
	for(int i=1;i<=n;i++)
	{
		diff+=(a[i]!=i);
		odd+=(abs(a[i]-i)&1);
	}
	int ans=0;
	F.init(n);
	for(int i=1;i<=n;i++)
	{
		ans+=(F.query(a[i]-1)&1);
		F.update(a[i],1);
	}
	ans&=1;
	while(q--)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		pair<int,int>res=Swap(u,v);
		diff+=res.first;odd+=res.second;
		ans^=1;
		if(!diff)
			printf("-1\n");
		else if(ans&1)
			printf("%d\n",n);
		else if(odd)
			printf("%d\n",n-1);
		else
			printf("%d\n",n-2);
	}
	
	return 0;
}