#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define pb push_back
#define lowbit(x) (x)&-(x)
using namespace std;
const int N=1e6+10;
int ans;
int n,m,T,a[N],ls[N],rs[N],f[N],stk[N],top,mx[N],len[N];
inline int read(){
	int s=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return f?-s:s;
}
inline void dfs(int x){
	if(!ls[x]&&!rs[x]){
		mx[x]=a[x];
		len[x]=1;
		f[x]=a[x]>0;
		return ;
	}
	if(!ls[x]||!rs[x]){
		int y=ls[x]+rs[x];
		dfs(y);
		mx[x]=mx[y];
		len[x]=len[y]+1;
		f[x]=max(f[y],min(len[x],a[x]+mx[x]));
	}else{
		dfs(ls[x]),dfs(rs[x]);
		mx[x]=max(mx[ls[x]],mx[rs[x]]);
		len[x]=len[ls[x]]+len[rs[x]]+1;
		f[x]=max({f[ls[x]],f[rs[x]],min(len[x],a[x]+mx[x])});
	}
}
inline void solve(){
	top=0;
	for(register int i=1;i<=n;++i) ls[i]=rs[i]=0;
	for(register int i=1;i<=n;++i){
		int lst=top;
		while(top&&a[i]<a[stk[top]]) --top;
		if(top) rs[stk[top]]=i;
		if(top<lst) ls[i]=stk[top+1];
		stk[++top]=i;
	}
	int rt=stk[1];
	dfs(rt);
	cout<<f[rt]<<'\n';
}
int main(){
	n=read(),T=read();
	for(register int i=1;i<=n;++i) a[i]=read();
	solve();
	while(T--){
		int k=read();
		while(k--){
			int x=read(),y=read();
			swap(a[x],a[y]);
		}
		solve();
	}
	return 0;
}