#include <cstdio> 
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
#include <map>
#include <cassert>
#include <queue>
#include <random>
#include <ctime>
#define int long long
using namespace std;

void read(int &x){
	x=0;
	int f=1;
	char c=getchar();
	while(!('0'<=c && c<='9')){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while('0'<=c && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	x*=f;
}
int n,m,a[1000010],ls[1000010],rs[1000010],len[1000010],mx[1000010],res[1000010];
int stk[1000010],tp=0;
void dfs(int k){
	if(!k){
		len[k]=0;
		mx[k]=-1e18;
		res[k]=-1e18;
		return;
	}
	dfs(ls[k]);
	dfs(rs[k]);
	//printf("[%lld %lld %lld]\n",a[k],ls[k],rs[k]);
	assert((!ls[k] || ls[k]<k) && (!rs[k] || k<rs[k]));
	assert((!ls[k] || a[ls[k]]>=a[k]) && (!rs[k] || a[rs[k]]>=a[k]));
	len[k]=len[ls[k]]+len[rs[k]]+1;
	mx[k]=max(a[k],max(mx[ls[k]],mx[rs[k]]));
	res[k]=max(res[ls[k]],res[rs[k]]);
	if(mx[ls[k]]+a[k]>len[ls[k]]){
		res[k]=max(res[k],min(len[k],mx[ls[k]]+a[k]));
	}
	if(mx[rs[k]]+a[k]>len[rs[k]]){
		res[k]=max(res[k],min(len[k],mx[rs[k]]+a[k]));
	}
}
int work(){
	tp=0;
	for(int i=1;i<=n;i++){
		ls[i]=rs[i]=0;
		while(tp && a[stk[tp]]>a[i]){
			ls[i]=stk[tp--];
		}
		if(tp){
			rs[stk[tp]]=i;
		}
		stk[++tp]=i;
	}
	dfs(stk[1]);
	return res[stk[1]];
}
signed main(){
	read(n);
	read(m);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	printf("%lld\n",work());
	while(m--){
		int siz,u,v;
		read(siz);
		while(siz--){
			read(u);
			read(v);
			swap(a[u],a[v]);
		}
		printf("%lld\n",work());
	}
	return 0;
}
/*
5 2
1 2 -2 3 4
1
2 3
1
1 2
*/