#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
//#define lll __int128
using namespace std;
const long long INF=1e9;
const long long mod=998244353;
//const long long mod=1000000007;
int n,m,Q;
int a[1000005],lo[1000005],P[55];
int p[21][1000005],p2[21][1000005];
namespace IO {
	const int SIZE=(1<<21)+1;
	char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f, qr;
	#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
	inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
	inline void putc(char x){*oS++=x;if(oS==oT)flush();}
	template <class I>
	inline void read(I &x){
		for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;
		for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;
	}
	template <class I>
	inline void print(I x){
		if(!x)putc('0');if(x<0)putc('-'),x=-x;
		while(x)qu[++qr]=x%10+'0',x/=10;
		while(qr)putc(qu[qr --]);
	}
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::putc;
using IO::print;
inline void st() {
	for(int j=1;(1<<j)<=n;j++) {
		for(int i=1;i+(1<<j)-1<=n;i++) {
			p[j][i]=min(p[j-1][i],p[j-1][i+(1<<j-1)]);
			p2[j][i]=max(p2[j-1][i],p2[j-1][i+(1<<j-1)]);
		}
	}
}
inline int ask(int x,int y) {
	int k=lo[y-x+1];
	return min(p[k][x],p[k][y-P[k]+1]);
}
inline int ask2(int x,int y) {
	int k=lo[y-x+1];
	return max(p2[k][x],p2[k][y-P[k]+1]);
}
inline bool check(int mid) {
	for(int i=mid;i<=n;i++) if(ask(i-mid+1,i)+ask2(i-mid+1,i)>mid) return 1;return 0;
}
inline void solve() {
	for(int i=1;i<=n;i++) p[0][i]=a[i],p2[0][i]=a[i];
	st();
	int l=1,r=n,res=0;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1,res=mid;
		else r=mid-1;
	}
	print(res),putc('\n');
}
signed main() {
	read(n),read(m);
	for(int i=1;i<=n;i++) read(a[i]),lo[i]=log2(i);
	P[0]=1;for(int i=1;i<=21;i++) P[i]=P[i-1]*2;
	solve();
	for(int i=1;i<=m;i++) {
		int k;read(k);
		for(int j=1,x,y;j<=k;j++) {
			read(x),read(y);
			swap(a[x],a[y]);
		}
		solve();
	}
	return 0;
}