#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n, m, a[N], l[N], b[N], ls[N], rs[N], stk[N], top, ans;

void dfs(int u){
	if(ls[u]) dfs(ls[u]);
	if(rs[u]) dfs(rs[u]);
	l[u] = l[ls[u]] + 1 + l[rs[u]];
	b[u] = max(a[u], max(b[ls[u]], b[rs[u]]));
	ans = max(ans, min(b[u] + a[u] - 1, l[u]));
	return ;
}

void solve(){
	top = 0;
	for(int i = 1; i <= n; i++){
		ls[i] = rs[i] = 0;
		int k = top;
		while(k > 0 && a[stk[k]] > a[i]) k--;
		if(k) rs[stk[k]] = i;
		if(k < top) ls[i] = stk[k + 1];
		stk[++k] = i;
		top = k;
	}

	ans = 0; b[0] = -1e9;
	dfs(stk[1]);
	cout << ans << "\n";
	return ;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];

	solve();
	for(int i = 1; i <= m; i++){
		int k; cin >> k;
		for(int i = 1; i <= k; i++){
			int x, y; cin >> x >> y;
			swap(a[x], a[y]);
		}
		solve();
	}
	return 0;
}