#include<bits/stdc++.h>
const int QWQ=1e6+5;
using namespace std;
inline int read(){
	int x=0,f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())
		if (ch=='-') f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())
		x=(x<<1)+(x<<3)+(ch^48);
	return x*f;
}
int stk[QWQ],top,L[QWQ],R[QWQ];
int n,T,a[QWQ],ans,siz[QWQ],mx[QWQ];
void dfs(int u){
	mx[u]=a[u],siz[u]=1;
	if (L[u]) dfs(L[u]),mx[u]=max(mx[L[u]],mx[u]),siz[u]+=siz[L[u]];
	if (R[u]) dfs(R[u]),mx[u]=max(mx[R[u]],mx[u]),siz[u]+=siz[R[u]];
	if (siz[u]==1){ ans=max(ans,a[u] ? 1:0); return ; }
	int v=mx[u]==mx[L[u]] ? L[u]:R[u];
	if (siz[v]+1>=a[u]+mx[u]) return ;
	ans=max(ans,min(siz[u],a[u]+mx[u]-1));
}
inline void solve(){
	a[0]=-1e9,top=0;
	for (int i=1,F;i<=n;stk[++top]=i++){
		for (F=0;top&&a[stk[top]]>a[i];top--,F=1);
		R[stk[top]]=i; if (F) L[i]=stk[top+1];
	}
	ans=0,dfs(0),printf("%d\n",ans);
}
signed main(){
	n=read(),T=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (solve();T--;solve())
		for (int m=read(),x,y;m--;)
			x=read(),y=read(),swap(a[x],a[y]);
	return 0;
}