UB了，90pts

#include <iostream>
#include <cstdio>
#include <map>
#include <cstdlib>
#include <ctime>
#define int long long
using namespace std;
struct node{
    int l,r,val,key;
    node(){
        l=r=key=val=0;
        return;
    }
}fhq[3000005];
int cnt;
struct BST{
    int root=0,x=0,y=0,size=0;
    inline void newnode(int val){
        ++cnt;
        fhq[cnt].l=fhq[cnt].r=0;
        fhq[cnt].val=val;
        fhq[cnt].key=rand();
        return;
    }
    inline void split(register int now,register int val,register int &x,register int &y){
        if (now==0){
            x=y=0;
            return;
        }
        if (fhq[now].val<=val){
            x=now;
            split(fhq[now].r,val,fhq[now].r,y);
        }
        else{
            y=now;
            split(fhq[now].l,val,x,fhq[now].l);
        }
        return;
    }
    inline int merge(register int x,register int y){
        if (x==0)return y;
        if (y==0)return x;
        if (fhq[x].key<fhq[y].key){
            fhq[x].r=merge(fhq[x].r,y);
            return x;
        }
        else{
            fhq[y].l=merge(x,fhq[y].l);
            return y;
        }
        return 0;
    }
    inline int pre(int val){
        split(root,val,x,y);
        if (x==0)return -114514;
        while(fhq[x].r)x=fhq[x].r;
        return fhq[x].val;
    }
    inline int nxt(int val){
        split(root,val,x,y);
        if (y==0)return -114514;
        while(fhq[y].l)y=fhq[y].l;
        return fhq[y].val;
    }
    inline void ins(int val){
        newnode(val);
        split(root,val,x,y);
        root=merge(x,merge(cnt,y));
        ++size;
        return;
    }
    inline void out(int now){
        if (now==0)return;
        out(fhq[now].l);
        printf("%d ",fhq[now].val);
        out(fhq[now].r);
    }
    inline void debug(){
        out(root);
        cout<<endl;
        return;
    }
}bst[2000005];
map <int,int>id;
int n,m,a[2000005],x[2000005],y[2000005],ans=2147483647;
int real[2000005];
int tot;
inline void dfs(int x,int y){
    if (x==0)return;
    int pr=bst[y].pre(fhq[x].val);
    int nx=bst[y].nxt(fhq[x].val);
    bst[y].ins(fhq[x].val);
    if (pr!=-114514)ans=min(ans,fhq[x].val-pr);
    if (nx!=-114514)ans=min(ans,nx-fhq[x].val);
    dfs(fhq[x].l,y);
    dfs(fhq[x].r,y);
    return;
}
inline void merge(int i,int j){
    if (bst[real[i]].size>bst[real[j]].size)swap(real[i],real[j]);
    dfs(bst[real[i]].root,real[j]);
    return;
}
signed main(){
    srand(time(NULL));
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        id[a[i]]=++tot;
    }
    for (int i=1;i<=m;i++){
        scanf("%d%d",&x[i],&y[i]);
        id[x[i]]=++tot,id[y[i]]=++tot;
    }
    for (int i=1;i<=n;i++)
        bst[id[a[i]]].ins(i);
    for (int i=1;i<=2000000;i++)real[i]=i;
    for (int i=1;i<=m;i++){
        if (id[x[i]]!=id[y[i]])merge(id[x[i]],id[y[i]]),id[x[i]]=++tot;
        printf("%d\n",ans);
    }
    return 0;
}