#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000005];
int l[1000005],r[1000005];
const int inf=0x3f3f3f3f;
int mx[1000005],sz[1000005],ans[1000005];
void dfs(int pos)
{
	if(l[pos])
		dfs(l[pos]);
	if(r[pos])
		dfs(r[pos]);
	mx[pos]=max({mx[l[pos]],mx[r[pos]],a[pos]});
	sz[pos]=sz[l[pos]]+sz[r[pos]]+1;
	ans[pos]=max(ans[l[pos]],ans[r[pos]]);
	if(a[pos]*2>1&&!l[pos]&&!r[pos])
		ans[pos]=1;
	if(mx[l[pos]]>mx[r[pos]])
		if(mx[l[pos]]+a[pos]>sz[l[pos]]+1)
			ans[pos]=max(ans[pos],min(mx[l[pos]]+a[pos]-1,sz[pos]));else;
	else
		if(mx[r[pos]]+a[pos]>sz[r[pos]]+1)
			ans[pos]=max(ans[pos],min(mx[r[pos]]+a[pos]-1,sz[pos]));else;
//	cout<<pos<<" "<<l[pos]<<" "<<r[pos]<<" "<<mx[pos]<<" "<<sz[pos]<<" "<<ans[pos]<<"\n";
}
void work()
{
	stack<int> z;
	int rt=0;
	for(int i=1;i<=n;i++)
	{
		l[i]=r[i]=0;
		int lst=0;
		while(!z.empty()&&z.top()>a[i])
			lst=z.top(),z.pop();
		if(!z.empty())
			r[z.top()]=i;
		else
			rt=i;
		l[i]=lst;
		z.push(i);
	}
	mx[0]=-inf;
	dfs(rt);
	cout<<ans[rt]<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	work();
	for(int i=1;i<=m;i++)
	{
		int k;
		cin>>k;
		for(int j=1;j<=k;j++)
		{
			int u,v;
			cin>>u>>v;
			swap(a[u],a[v]);
		}
		work();
	}
}
/*
10 0
100 99 100 94 98 -99 -100 -97 -97 -98
*/