#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,N=1e6+7;
ll n,m,a[N],s[N][2],rt;
ll mx[N],dp[N];
void dac(ll p,ll l,ll r) {
	if (l==r) mx[p]=a[p],dp[p]=a[p]+a[p]>1;
	else if (p==l)
		dac(s[p][1],p+1,r),
		mx[p]=mx[s[p][1]],dp[p]=mx[p]+a[p]>r-l+1?r-l+1:dp[s[p][1]];
	else if (p==r)
		dac(s[p][0],l,p-1),mx[p]=mx[s[p][0]],dp[p]=mx[p]+a[p]>r-l+1?r-l+1:dp[s[p][0]];
	else {
		ll sl=p-l,sr=r-p,cl=s[p][0],cr=s[p][1];
		dac(cl,l,p-1),dac(cr,p+1,r);
		mx[p]=max(mx[cl],mx[cr]),dp[p]=max(dp[cl],dp[cr]);
		if (mx[cl]<mx[cr]) swap(sl,sr),swap(cl,cr);
		if (mx[p]+a[p]>sl+1) dp[p]=sl+1+min(mx[p]+a[p]-sl-2,sr);
	}
	// printf("%lld %lld %lld %lld %lld\n",p,l,r,mx[p],dp[p]);
}
void solve() {
	stack<ll> st;
	for (ll i=1;i<=n;i++) {
		while (st.size()&&a[st.top()]>a[i]) s[i][0]=st.top(),st.pop();
		if (st.size()) s[st.top()][1]=i;
		else rt=i;
		st.push(i);
	}
	dac(rt,1,n);
	cout<<dp[rt]<<"\n";
}
void mian() {
	scanf("%lld%lld",&n,&m);
	for (ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	solve();
	for (ll x,y,z;m--;) {
		scanf("%lld",&x);
		for (ll i=1;i<=x;i++) scanf("%lld%lld",&y,&z),swap(a[y],a[z]);
		solve();
	}
}
bool ORY; int main() {
	// freopen("test.out","w",stdout);
	// while (1)
	// int t; for (scanf("%d",&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB\n";
	return 0;
}