/*

    LibreOJ #516. 「LibreOJ β Round #2」DP 一般看规律

    set启发式合并

    题目中给定的代码意思求相同的数中间隔最小的值。

    那么维护n个set就好

    合并时把小的向大的上暴力合并

    用了map所以不用离散化

*/

#include <iostream>

#include <cstdio>

#include <set>

#include <map>

#define INF 2147483647

void read (int &now)

{

    register char word = getchar ();

    int temp = ;

    for (; !isdigit (word); word = getchar ())

        if (word == '-')

            temp = ;

    for (now = ; isdigit (word); now = now *  + word - '', word = getchar ());

    if (temp)

        now = -now;

}

std :: map <int, std :: set <int> > Need;

int N, M;

int Answer = INF;

inline int min (int a, int b)

{

    return a < b ? a : b;

}

inline void Insert (int pos, int x)

{

    std :: set <int> :: iterator now = Need[pos].lower_bound (x);

    if (now != Need[pos].end ())

        Answer = min (Answer, *now - x);

    if (now != Need[pos].begin ())

        Answer = min (Answer, x - *-- now);

    Need[pos].insert (x);

}

int main (int argc, char *argv[])

{

    read (N), read (M);

    int x, y;

    for (int i = ; i <= N; i ++)

    {

        read (x);

        Insert (x, i);

    }

    for (; M; -- M)

    {

        read (x), read (y);

        if (x != y)

        {

            if (Need[x].size () > Need[y].size ())

                std :: swap (Need[x], Need[y]);

            for (std :: set <int> :: iterator i = Need[x].begin (); i != Need[x].end (); ++ i)

                Insert (y, *i);

            Need[x].clear ();

        }

        printf ("%d\n", Answer);

    }

    return ;

}