#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#define N 100000
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,lg[N+1],a[N+1],b[N+1],c[N+1],block[N+1],num[N+1],ans;
vector<int>p[N+1];
vector<int>v[N+1];
vector<unsigned long long>w[N+1];
unsigned long long seed,rd[N+1],delta[N+1];
unsigned long long RAND()
{
    seed=(seed<<7)^seed;
    seed=(seed>>13)^seed;
    seed=(seed<<17)^seed;
    return seed;
}
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;
}
void spread(int x)
{
    int res=0;
    for (int i=0;i<p[x].size();++i) res^=v[x][i],num[p[x][i]]^=res;
    for (int i=0;i<v[x].size();++i) v[x][i]=0;
    return;
}
void rebuild(int x,int d1,int d2)
{
    bool op=0,op2=0;
    vector<int>q;
    if (d1&&d2&&a[d1]>a[d2]) swap(d1,d2);
    for (int i=0;i<p[x].size();++i)
	if (p[x][i]!=d1&&p[x][i]!=d2)
	{
	    if (!op&&d1&&a[d1]<a[p[x][i]]) op=1,q.push_back(d1);
	    if (!op2&&d2&&a[d2]<a[p[x][i]]) op2=1,q.push_back(d2);
	    q.push_back(p[x][i]);
	}
    if (!op&&d1) q.push_back(d1);
    if (!op2&&d2) q.push_back(d2);
    p[x]=q,delta[x]=0;
    for (int i=0;i<p[x].size();++i)
    {
	w[x][i]=rd[p[x][i]];
	if (num[p[x][i]]) delta[x]^=rd[p[x][i]];
	if (i) w[x][i]^=w[x][i-1];
    }
    return;
}
void change(int x,int l,int r)
{
    int sl=-1,sr=-1;
    for (int i=lg[p[x].size()];i>=0;--i)
	if (sl+(1<<i)<p[x].size()&&a[p[x][sl+(1<<i)]]<l)
	    sl+=(1<<i);
    sl++;
    for (int i=lg[p[x].size()];i>=0;--i)
	if (sr+(1<<i)<p[x].size()&&a[p[x][sr+(1<<i)]]<=r)
	    sr+=(1<<i);
    if (sl<v[x].size()) v[x][sl]^=1;
    if (sr+1<v[x].size()) v[x][sr+1]^=1;
    delta[x]^=(w[x][sr]^(sl?w[x][sl-1]:0));
    return;
}
int query(int x,int l,int r)
{
    int sl=-1,sr=-1;
    for (int i=lg[p[x].size()];i>=0;--i)
	if (sl+(1<<i)<p[x].size()&&a[p[x][sl+(1<<i)]]<l)
	    sl+=(1<<i);
    sl++;
    for (int i=lg[p[x].size()];i>=0;--i)
	if (sr+(1<<i)<p[x].size()&&a[p[x][sr+(1<<i)]]<=r)
	    sr+=(1<<i);
    return (sr-sl+1)&1;
}
void adder(int x,int y)
{
    int res=0,res2=0;
    for (int i=block[x]+1;i<=block[y]-1;++i) res^=query(i,1,a[x]),res2^=query(i,1,a[y]),change(i,min(a[x],a[y]),max(a[x],a[y]));
    if (block[x]==block[y])
    {
	spread(block[x]);
	for (int i=x+1;i<=y-1;++i)
	{
	    if (min(a[x],a[y])<a[i]&a[i]<max(a[x],a[y])) num[i]^=1;
	    if (a[i]<a[x]) res^=1;
	    if (a[i]<a[y]) res2^=1;
	}
	swap(a[x],a[y]),num[x]^=res,num[y]^=res2,swap(num[x],num[y]);
	if (a[x]>a[y]) num[x]^=1;
	else num[y]^=1;
	rebuild(block[x],x,y);
    }
    else
    {
	spread(block[x]),spread(block[y]);
	for (int i=x+1;i<=min(block[x]*sz,n);++i)
	{
	    if (min(a[x],a[y])<a[i]&&a[i]<max(a[x],a[y])) num[i]^=1;
	    if (a[i]<a[x]) res^=1;
	    if (a[i]<a[y]) res2^=1;
	}
	for (int i=(block[y]-1)*sz+1;i<=y-1;++i)
	{
	    if (min(a[x],a[y])<=a[i]&&a[i]<=max(a[x],a[y])) num[i]^=1;
	    if (a[i]<a[x]) res^=1;
	    if (a[i]<a[y]) res2^=1;
	}
	swap(a[x],a[y]),num[x]^=res,num[y]^=res2,swap(num[x],num[y]);
	if (a[x]>a[y]) num[x]^=1;
	else num[y]^=1;
	rebuild(block[x],x,0),rebuild(block[y],y,0);
    }
    return;
}
int calc()
{
    for (int i=1;i<=block[n];++i) spread(i);
    int ps=0;
    for (int i=block[n];i>=1;--i)
	if (delta[i])
	{
	    spread(i);
	    for (int j=min(i*sz,n);j>=(i-1)*sz+1;--j)
		if (num[j])
		{
		    ps=j;
		    break;
		}
	    break;
	}
    return ps+1;
}
bool cmp(int x,int y)
{
    return a[x]<a[y];
}
int main()
{
    int x,y;
    n=read(),q=read(),sz=sqrt(n*log(n)/log(2)),seed=time(0);
    for (int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
    for (int i=1;i<=n;++i) a[i]=read(),block[i]=(i-1)/sz+1,rd[i]=RAND();
    for (int i=n;i>=1;--i) num[i]=query(a[i]),add(a[i],1);
    for (int i=1;i<=block[n];++i)
    {
	for (int j=(i-1)*sz+1;j<=min(i*sz,n);++j) p[i].push_back(j);
	sort(p[i].begin(),p[i].end(),cmp),v[i].resize(p[i].size()),w[i].resize(p[i].size());
	for (int j=0;j<p[i].size();++j)
	{
	    w[i][j]=rd[p[i][j]];
	    if (num[p[i][j]]) delta[i]^=rd[p[i][j]];
	    if (j) w[i][j]^=w[i][j-1];
	}
    }
    while (q--)
    {
	x=read(),y=read();
	if (x>y) swap(x,y);
	adder(x,y),printf("%d\n",calc());
    }
    return 0;
}