//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define Ma 1000005
#define G 3
#define pb push_back
#define L (1<<21)
#define all(x) x.begin(),x.end()
using namespace std;
ll n,m;
ll a[Ma],b[Ma];
ll ans=0;
ll f[Ma];
ll cnt=0,cnt2=0,cnt3=0;

void merage(ll l,ll r)
{
    if (l==r)
        return ;
    ll mid=(l+r)>>1;
    merage(l,mid),merage(mid+1,r);
    ll i=l,j=mid+1,k=0;
    while (i<=mid&&j<=r){
        if (a[i]<=a[j]) b[k++]=a[i++];
        else ans+=mid-i+1,b[k++]=a[j++];
    }
    while (j<=r) b[k++]=a[j++];
    while (i<=mid) b[k++]=a[i++];
    for (ll k=0;k<r-l+1;k++)
        a[l+k]=b[k];
    return;
}

void add(ll x,ll id)
{
    f[id]=x;
    if (f[id]==id) cnt++;
    if (id==1&&(n&1))
        cnt2+=(f[id]==1);
    else
    {
        ll ch=(n+id)&1;
        if (ch)
        {
            if (f[id+1]==f[id]+1)
                cnt2++;
        }
        else
        {
            if (f[id-1]==f[id]-1)
                cnt2++;
        }
    }
    if (id==1&&(n&1))
        cnt3+=(f[id]==n);
    else
    {
        ll ch=(n+id)&1;
        if (ch)
        {
            if (f[id+1]==f[id]-1)
                cnt3++;
        }
        else
        {
            if (f[id-1]==f[id]+1)
                cnt3++;
        }
    }
}

void del(ll x,ll id)
{
    if (f[id]==id) cnt--;
    if (id==1&&(n&1))
        cnt2-=(f[id]==1);
    else
    {
        ll ch=(n+id)&1;
        if (ch)
        {
            if (f[id+1]==f[id]+1)
                cnt2--;
        }
        else
        {
            if (f[id-1]==f[id]-1)
                cnt2--;
        }
    }
    if (id==1&&(n&1))
        cnt3+=(f[id]==n);
    else
    {
        ll ch=(n+id)&1;
        if (ch)
        {
            if (f[id+1]==f[id]-1)
                cnt3--;
        }
        else
        {
            if (f[id-1]==f[id]+1)
                cnt3--;
        }
    }
    f[id]=-1;
}

void sol()
{
    cin>>n>>m;
    for (ll i=1;i<=n;i++)
        cin>>a[i],f[i]=a[i];
    for (ll i=1;i<=n;i++)
        cnt+=(i==f[i]);
    if (n&1)
    {
        cnt2+=(f[1]==1);
        cnt3+=(f[1]==n);
        for (ll i=2;i<=n;i+=2)
            cnt2+=(f[i+1]-f[i]==1);
        for (ll i=2;i<=n;i+=2)
            cnt3+=(f[i+1]-f[i]==-1);
    }
    else
    {
        for (ll i=1;i<=n;i+=2)
            cnt2+=(f[i+1]-f[i]==1);
        for (ll i=1;i<=n;i+=2)
            cnt3+=(f[i+1]-f[i]==-1);
    }
    merage(1,n);
    ll ca=0;
    for (ll i=1;i<=m;i++)
    {
        ll x,y;
        cin>>x>>y;
        ll px=f[x],py=f[y];
        del(px,x),del(py,y);
        add(py,x),add(px,y);
       // printf("cnt=%lld\n",cnt);
        if (n==1)
            printf("-1\n");
        else if (n==2)
        {
            if ((ans+i)&1)
                printf("%lld\n",n);
            else
                printf("-1\n");
        }
        else if (cnt==n)
            printf("-1\n");
        else if ((ans+i)&1)
            printf("%lld\n",n);
        else if (cnt2==(n+1)/2||((n&1)&&cnt3==(n+1)/2))
            printf("%lld\n",n-2);
        else
            printf("%lld\n",n-1);
    }
}

int	main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll tt=1;
    //cin>>tt;
   while (tt--)
        sol();
    return 0;
}
/*500000 500000*/