# include <bits/stdc++.h>
using namespace std;
const int B=1300;
int n,a[100010],id[100010],pos[100010],b[100010],blo[100010],cnt1[1010],L[1010],R[1010];
bool val[100010],d[100010];
struct BIT
{
	int s[100010];
	void update(int x){for(int i=x;i<=n;i+=i&(-i)) s[i]^=1;}
	int query(int x)
	{
		int ans=0;
		for(int i=x;i;i-=i&(-i)) ans^=s[i];
		return ans;
	}
}T;
void pushdown(int i)
{
	int l=L[i],r=R[i];
	val[id[l]]=d[l];
	for(int j=l+1,s=d[l];j<=r;j++) val[id[j]]=(s^=d[j]);
}
void build(int i)
{
	int l=L[i],r=R[i];
	for(int j=l;j<=r;j++) d[j]=val[id[j]];
	cnt1[i]=d[l];
	for(int j=r;j>l;j--) d[j]^=d[j-1],cnt1[i]+=d[j];
}
void update(int x,int y,int z) // a[x] <-- y , val[x] = z
{
	int l=L[blo[x]],r=R[blo[x]],p=pos[x];
	a[x]=y;val[x]=z;
	copy(id+p+1,id+r+1,id+p);
	copy(b+p+1,b+r+1,b+p);b[r]=n+1;
	for(int i=l;i<=r;i++)
		if(y<b[i])
		{
			copy_backward(id+i,id+r,id+i+1);
			copy_backward(b+i,b+r,b+i+1);
			id[i]=x;b[i]=y;pos[x]=i;
			break;
		}
	build(blo[x]);
}
void update2(int i,int x,int y) // x ~ y : val^=1
{
	int l=L[i],r=R[i];
	x=lower_bound(b+l,b+r+1,x)-b;
	y=upper_bound(b+x,b+r+1,y)-b;
	if(x<=r) cnt1[i]-=d[x],d[x]^=1,cnt1[i]+=d[x];
	if(y<r) cnt1[i]-=d[y],d[y]^=1,cnt1[i]+=d[y];
}
void update2(int l,int r,int x,int y)
{
	if(l>r || x>y) return;
	if(blo[l]==blo[r])
	{
		pushdown(blo[l]);
		for(int j=l;j<=r;j++)
			if(x<=a[j] && a[j]<=y) val[j]^=1;
		build(blo[l]);
		return;
	}
	pushdown(blo[l]);pushdown(blo[r]);
	for(int i=l;i<=R[blo[l]];i++)
		if(x<=a[i] && a[i]<=y) val[i]^=1;
	for(int i=L[blo[r]];i<=r;i++)
		if(x<=a[i] && a[i]<=y) val[i]^=1;
	build(blo[l]);build(blo[r]);
	for(int i=blo[l]+1;i<blo[r];i++) update2(i,x,y);
}
bool query(int x,int y) // # { a[i]<=y : i>=x }
{
	if(x>n) return 0;
	int ans=0;
	for(int i=x;i<=R[blo[x]];i++)
		if(a[i]<=y) ans^=1;
	for(int i=blo[x]+1;i<=blo[n];i++)
		ans^=(upper_bound(b+L[i],b+R[i]+1,y)-b-L[i])&1;
	return ans;
}
int query()
{
	for(int i=blo[n];i>=1;i--)
		if(cnt1[i])
		{
			pushdown(i);
			for(int j=R[i];;j--)
				if(val[j]) return j;
		}
	return 0;
}
int main()
{
	int q,x,y;
	cin>>n>>q;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),blo[i]=(i-1)/B+1;
	for(int i=1;i<=blo[n];i++) L[i]=(i-1)*B+1,R[i]=min(i*B,n);
	iota(id+1,id+n+1,1);
	for(int i=n;i>=1;i--) val[i]=T.query(a[i]),T.update(a[i]);
	for(int i=1;i<=blo[n];i++)
	{
		int l=L[i],r=R[i];
		sort(id+l,id+r+1,[](int j,int k){return a[j]<a[k];});
		for(int j=l;j<=r;j++) b[j]=a[id[j]],pos[id[j]]=j;
		build(i);
	}
	while(q--)
	{
		scanf("%d%d",&x,&y);
		if(x>y) swap(x,y);
		int v1=a[x],v2=a[y],t1=query(x,v2-1),t2=query(y+1,v1-1);
		update(x,v2,t1);update(y,v1,t2);
		update2(x+1,y-1,min(v1,v2)+1,max(v1,v2)-1);
		printf("%d\n",query()+1);
	}
	return 0;
}