#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin>>n>>q;
	int arr[n+1],even = 0, sorted = 0;
	for(int i = 1; i <= n; i++){
		cin>>arr[i];
		if(arr[i] % 2 == i % 2) even++;
		if(arr[i] == i)	sorted++;
	}
	int now = (even != n);
	while(q--){
		int a, b;
		cin>>a>>b;
		if(arr[a] % 2 == a % 2)	even--;
		if(arr[b] % 2 == b % 2) even--;
		if(arr[a] == a)	sorted--;
		if(arr[b] == b)	sorted--;
		swap(arr[a], arr[b]);
		if(arr[a] % 2 == a % 2)	even++;
		if(arr[b] % 2 == b % 2) even++;
		if(arr[a] == a)	sorted++;
		if(arr[b] == b)	sorted++;
		
		now ^= 1;
		if(now)	cout<<n<<"\n";
		else if(even != n)	cout<<n-1<<"\n";
		else if(sorted != n)	cout<<n-2<<"\n";
		else cout<<-1<<"\n";
	}
	return 0;
}