#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <algorithm>
#define fi first
#define se second
#define ep emplace
#define MISAKA main
#define ll long long
#define eb emplace_back
#define pii pair<int,int>
#define rg(x) x.begin(),x.end()
#define pc(x) __builtin_popcount(x)
#define mems(a,x) memset(a,x,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _rep(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define FIO(FILE) freopen(FILE".in","r",stdin),freopen(FILE".out","w",stdout)
using namespace std;
bool __st;
inline int read(){
    char c=getchar();int f=1,x=0;
    for(;c<48||c>57;c=getchar())if(c=='-') f=-1;
    for(;47<c&&c<58;c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
const int N=1e6+10,mod=998244353;
int n,m,a[N],s[N],ls[N],sz[N],rs[N],mx[N],ans,top;
void dfs(int u){
    if(ls[u]) dfs(ls[u]);
    if(rs[u]) dfs(rs[u]);
    sz[u]=sz[ls[u]]+sz[rs[u]]+1;
    mx[u]=max({mx[ls[u]],mx[rs[u]],a[u]});
    if(ls[u]&&mx[ls[u]]+a[u]>=sz[ls[u]]+1) ans=max(ans,min(sz[u],mx[ls[u]]+a[u]));
    if(rs[u]&&mx[rs[u]]+a[u]>=sz[rs[u]]+1) ans=max(ans,min(sz[u],mx[rs[u]]+a[u]));
    if(a[u]>=1) ans=max(ans,1);
}
void solve(){
    rep(i,0,n) ls[i]=rs[i]=sz[i]=mx[i]=s[i]=0;top=0;
    rep(i,1,n){
        int p=0;
        while(top&&a[s[top]]>a[i]) p=rs[s[top-1]]=s[top],top--;
        ls[i]=p;s[++top]=i;
    }
    while(top) rs[s[top-1]]=s[top],top--;
    ans=0;dfs(rs[0]);
    printf("%d\n",ans);
}
void misaka(){
    n=read(),m=read();
    rep(i,1,n) a[i]=read();
    solve();
    while(m--){
        int k=read(),x,y;
        while(k--) x=read(),y=read(),swap(a[x],a[y]);
        solve();
    }
}
bool __ed;
signed MISAKA(){
    #ifdef LOCAL_MSK
    atexit([](){
    debug("\n%.3lfs  ",(double)clock()/CLOCKS_PER_SEC);
    debug("%.3lfMB\n",abs(&__st-&__ed)/1024./1024);});
    #endif
    
    int T=1;
    while(T--) misaka();
    return 0;
}