#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#include<bitset>
#define N 100000
#define M 317
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int lowbit(int x)
{
    return x&(-x);
}
int n,q,sz,block[N+1],a[N+1],b[N+1],c[N+1];
bitset<N+1>B[M+1];
bitset<N+1>W[M+1];
bitset<N+1>zero;
bitset<N+1>ans;
void add(int x,int d)
{
    for (;x<=n;x+=lowbit(x)) c[x]^=d;
    return;
}
int query(int x)
{
    int res=0;
    for (;x>=1;x-=lowbit(x)) res^=c[x];
    return res;
}
bitset<N+1>get(int x)
{
    if (!x) return zero;
    bitset<N+1>res=W[block[x]-1];
    for (int i=(block[x]-1)*sz+1;i<=x;++i) res[n-b[i]+1].flip();
    return res;
}
bitset<N+1>calc(int x)
{
    if (!x) return zero;
    bitset<N+1>res=B[block[x]-1];
    for (int i=(block[x]-1)*sz+1;i<=x;++i) res[n-i+1].flip();
    return res;
}
int main()
{
    int x,y;
    bool op,op2;
    n=read(),q=read(),sz=sqrt(n);
    for (int i=1;i<=n;++i) a[i]=read(),b[a[i]]=i,block[i]=(i-1)/sz+1;
    for (int i=1;i<=n;++i) B[block[i]][n-i+1]=W[block[a[i]]][n-i+1]=1;
    for (int i=n;i>=1;--i)
    {
	if (query(a[i])) ans[n-i+1]=1;
	add(a[i],1);
    }
    for (int i=1;i<=block[n];++i) B[i]|=B[i-1],W[i]|=W[i-1];
    while (q--)
    {
	x=read(),y=read();
	if (x>y) swap(x,y);
	ans^=(get(max(a[x],a[y]))^get(min(a[x],a[y])-1))&(calc(y-1)^calc(x)),op=(get(a[x])&(calc(y-1)^calc(x))).count()&1,op2=(get(a[y])&(calc(y-1)^calc(x))).count()&1;
	if (op) ans[n-x+1].flip();
	if (op2) ans[n-y+1].flip();
	swap(a[x],a[y]),swap(b[a[x]],b[a[y]]);
	for (int i=1;i<=block[n];++i) op=W[i][n-x+1],op2=W[i][n-y+1],W[i][n-x+1]=op2,W[i][n-y+1]=op;
	op=ans[n-x+1],op2=ans[n-y+1],ans[n-x+1]=op2,ans[n-y+1]=op;
	if (a[x]<a[y]) ans[n-y+1].flip();
	else ans[n-x+1].flip();
	printf("%d\n",(int)(n-ans._Find_first()+2));
    }
    return 0;
}