#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,q,a[100005],x,y;
struct BIT{
	int tree[100005];
	void add(int p,int v){
		while(p<=n)tree[p]+=v,p+=(p&(-p));
		return;
	}
	int ask(int p){
		int ans=0;
		while(p)ans+=tree[p],p-=(p&(-p));
		return ans;
	}
}T[325],_T;
const int B=320;
int B_tot,B_pos[1005],B_id[100005];
int f[100005],_f[100005];
void upd(int x){
	int id=B_id[x]-1;
	int cnt=T[id].ask(a[x]);
	for (int i=B_pos[id]-1;i>x;i--)
		if (a[i]<a[x])cnt++;
	f[x]=(cnt&1);
	return;
}
int len[325],val[325][325],ch[325][325];
int cnt[325];
void pushup(int id){
	int l=B_pos[id],r=B_pos[id-1]-1;
	len[id]=0;
	for (int i=r;i>=l;i--){
		f[i]=((T[id-1].ask(a[i])+_T.ask(a[i]))&1);
		_T.add(a[i],1);
	}
	for (int i=r;i>=l;i--)_T.add(a[i],-1);
	for (int i=l;i<=r;i++){
		val[id][++len[id]]=a[i];
		_f[a[i]]=f[i];
	}
	sort(val[id],val[id]+1+len[id]);
	cnt[id]=0;
	for (int i=1;i<=len[id];i++){
		ch[id][i]=(_f[val[id][i]]^_f[val[id][i-1]]);
		if (ch[id][i]==1)cnt[id]++;
	}
	for (int i=l;i<=r;i++)_f[a[i]]=0;
	return;
}
void pushdown(int id){
	int l=B_pos[id],r=B_pos[id-1]-1;
	for (int i=1;i<=len[id];i++){
		ch[id][i]^=ch[id][i-1];
		_f[val[id][i]]=(_f[val[id][i-1]]^ch[id][i]);
	}
	for (int i=l;i<=r;i++)f[i]=_f[a[i]];
	for (int i=1;i<=len[id];i++)_f[val[id][i]]=0;
	return;
}
int ge(int id,int x){
	int l=1,r=len[id],ans=len[id]+1;
	while(l<=r){
		int mid=(l+r)/2;
		if (val[id][mid]>=x)ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
int le(int id,int x){
	int l=1,r=len[id],ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if (val[id][mid]<=x)ans=mid,l=mid+1;
		else r=mid-1; 
	}
	return ans;
}
void mdf(int id,int l,int r){
	int pl=ge(id,l),pr=le(id,r);
	if (pl<=len[id]&&pr>=1){
		ch[id][pl]^=1;
		if (ch[id][pl]==0)cnt[id]--;
		else cnt[id]++;
		ch[id][pr+1]^=1;
		if (ch[id][pr+1]==0)cnt[id]--;
		else cnt[id]++;
	}
	return;
}
int main(){
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	B_pos[0]=n+1;
	for (int i=n;i>=1;i--)
		if (i==1||(n-i+1)%B==0)B_pos[++B_tot]=i;
	for (int i=1;i<=B_tot;i++)
		for (int j=B_pos[i];j<B_pos[i-1];j++)B_id[j]=i;
	for (int i=1;i<=B_tot;i++){
		int p=B_pos[i];
		for (int j=n;j>=p;j--)T[i].add(a[j],1);
	}
	for (int i=1;i<=B_tot;i++)pushup(i);
	while(q--){
		scanf("%d%d",&x,&y);
		if (x>y)swap(x,y);
		int l=a[x],r=a[y];
		if (l>r)swap(l,r);
		swap(a[x],a[y]);
		for (int i=1;i<=B_tot;i++){
			int p=B_pos[i];
			if (p>x&&p<=y)T[i].add(a[y],-1),T[i].add(a[x],1);
		}
		for (int i=B_id[y]+1;i<=B_id[x]-1;i++)mdf(i,l,r);
		pushup(B_id[x]);
		if (B_id[x]!=B_id[y])pushup(B_id[y]);
		int ans=n+1;
		for (int i=1;i<=B_tot;i++){
			if (cnt[i]>0)break;
			ans=B_pos[i];
		}
		if (ans>1)pushdown(B_id[ans]+1);
		while(ans>1&&f[ans-1]==0)ans--;
		printf("%d\n",ans);
	}
	return 0;
}