#include <bits/stdc++.h>
const int N=2e5+5;

int n,q,x,y,z,a[N];

struct BIT
{
    int c[N];

    void Add(int x){for ( ; x<=n; x+=x&-x) c[x]^=1;}

    int Sum(int x){int E=0; for ( ; x; x-=x&-x) E^=c[x]; return E;}
}T;

int main()
{
    scanf("%d%d",&n,&q); int i,j;
    for (i=1; i<=n; i++) scanf("%d",a+i),x+=a[i]==i,y+=(a[i]+i&1);
    for (i=n; i; i--) z^=T.Sum(a[i]),T.Add(a[i]);
    printf("%d %d %d\n",x,y,z);

    while (q--)
    {
        scanf("%d%d",&i,&j),x-=(a[i]==i)+(a[j]==j),y-=(a[i]+i&1)+(a[j]+j&1);
        std::swap(a[i],a[j]),x+=(a[i]==i)+(a[j]==j),y+=(a[i]+i&1)+(a[j]+j&1),z^=1;
        if (z&1) printf("%d\n",n);
        else if (x==n) puts("-1");
        else printf("%d\n",n-1-!y);
    }

    return 0;
}