#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("tests.in" , "r" , stdin) ;

ll mod = 1e9+7 ;

const int N = 2e5+23;

int fen[N], a[N];

int inv[N];

int all;
int is;
int n;
int q;


int kir;
void upd(int x){
    for(x=n+1-x; x<N; x+=x&-x) fen[x]++;
}

int get(int x){
    int ans=0;
    for (x=n+1-x; x>0; x-=x&-x) ans+=fen[x];
    return ans;
}


int main()
{
    fast_io
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>a[i];

    for (int i=1; i<=n; i++){
        inv[i]=get(i)%2;
        kir+=get(a[i]);
        upd(a[i]);
        if(a[i]==i) is++;
    }
    for (int i=0; i<N; i++) fen[i]=0;
    for (int i=n; i>0; i--){
        inv[i]=(inv[i]+n-i-get(a[i]))%2;
        upd(a[i]);
        all+=inv[i];
    }

    while(q--){
        int i, j; cin>>i>>j;
        kir^=1;
        if(a[i]==i) is--;
        if(a[j]==j) is--;
        all-=inv[i]+inv[j];
        swap(a[i], a[j]); swap(inv[i], inv[j]); swap(i, j);

        if(a[i]==i) is++;
        if(a[j]==j) is++;

        inv[i]^=abs(i-j)%2; inv[j]^=abs(i-j)%2;

        all+=inv[i]+inv[j];
        if(kir&1)cout<<n<<endl;
        else {
            if(is==n) cout<<-1<<endl;
            else if(all) cout<<n-1<<endl;
            else cout<<n-2<<endl;
        }
    }

}