You have a set of n discs, the i-th disc has radius i. Initially, these discs are split among m towers: each tower contains at least one disc, and the discs in each tower are sorted in descending order of their radii from bottom to top.

You would like to assemble one tower containing all of those discs. To do so, you may choose two different towers i and j (each containing at least one disc), take several (possibly all) top discs from the tower i and put them on top of the tower j in the same order, as long as the top disc of tower j is bigger than each of the discs you move. You may perform this operation any number of times.

For example, if you have two towers containing discs [6, 4, 2, 1] and [8, 7, 5, 3] (in order from bottom to top), there are only two possible operations:

  * move disc 1 from the first tower to the second tower, so the towers are [6, 4, 2] and [8, 7, 5, 3, 1]; 
  * move discs [2, 1] from the first tower to the second tower, so the towers are [6, 4] and [8, 7, 5, 3, 2, 1]. 



Let the difficulty of some set of towers be the minimum number of operations required to assemble one tower containing all of the discs. For example, the difficulty of the set of towers [[3, 1], [2]] is 2: you may move the disc 1 to the second tower, and then move both discs from the second tower to the first tower.

You are given m - 1 queries. Each query is denoted by two numbers a_i and b_i, and means "merge the towers a_i and b_i" (that is, take all discs from these two towers and assemble a new tower containing all of them in descending order of their radii from top to bottom). The resulting tower gets index a_i.

For each k ∈ [0, m - 1], calculate the difficulty of the set of towers after the first k queries are performed.

Input

The first line of the input contains two integers n and m (2 ≤ m ≤ n ≤ 2 ⋅ 10^5) — the number of discs and the number of towers, respectively.

The second line contains n integers t_1, t_2, ..., t_n (1 ≤ t_i ≤ m), where t_i is the index of the tower disc i belongs to. Each value from 1 to m appears in this sequence at least once.

Then m - 1 lines follow, denoting the queries. Each query is represented by two integers a_i and b_i (1 ≤ a_i, b_i ≤ m, a_i ≠ b_i), meaning that, during the i-th query, the towers with indices a_i and b_i are merged (a_i and b_i are chosen in such a way that these towers exist before the i-th query).

Output

Print m integers. The k-th integer (0-indexed) should be equal to the difficulty of the set of towers after the first k queries are performed.

Example

Input


7 4
1 2 3 3 1 4 3
3 1
2 3
2 4


Output


5
4
2
0

Note

The towers in the example are:

  * before the queries: [[5, 1], [2], [7, 4, 3], [6]]; 
  * after the first query: [[2], [7, 5, 4, 3, 1], [6]]; 
  * after the second query: [[7, 5, 4, 3, 2, 1], [6]]; 
  * after the third query, there is only one tower: [7, 6, 5, 4, 3, 2, 1]. 
import java.io.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class cf1380e_4 {

    static int par[];

    static int find(int i) {
        return i == par[i] ? i : (par[i] = find(par[i]));
    }

    static void union(int i, int j) {
        int a = find(i), b = find(j);
        par[b] = a;
    }

    public static void main(String[] args) throws IOException {
        int n = rni(), m = ni(), t[] = ria(n);
        par = new int[m];
        for(int i = 0; i < m; ++i) {
            par[i] = i;
        }
        List<TreeSet<Integer>> towers = new ArrayList<>();
        for(int i = 0; i < m; ++i) {
            towers.add(new TreeSet<>());
        }
        for(int i = 0; i < n; ++i) {
            towers.get(--t[i]).add(i);
        }
        int ans = 0;
        for(int i = 1; i < n; ++i) {
            if(t[i] != t[i - 1]) {
                ++ans;
            }
        }
        prln(ans);
        for(int i = 1; i < m; ++i) {
            int a = find(rni() - 1), b = find(ni() - 1);
            // --ans;
            if(towers.get(a).size() < towers.get(b).size()) {
                int __swap = a;
                a = b;
                b = __swap;
            }
            union(a, b);
            for(int j : towers.get(b)) {
                if(j > 0 && t[j - 1] == a) {
                    --ans;
                }
                if(j < n - 1 && t[j + 1] == a) {
                    --ans;
                }
            }
            for(int j : towers.get(b)) {
                towers.get(a).add(j);
                t[j] = a;
            }
            prln(ans);
            // prln(t);
        }
        close();
    }

    static BufferedReader __in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter __out = new PrintWriter(new OutputStreamWriter(System.out));
    static StringTokenizer input;
    static Random rand = new Random();

    // references
    // IBIG = 1e9 + 7
    // IRAND ~= 3e8
    // IMAX ~= 2e10
    // LMAX ~= 9e18
    // constants
    static final int IBIG = 1000000007;
    static final int IRAND = 327859546;
    static final int IMAX = 2147483647;
    static final int IMIN = -2147483648;
    static final long LMAX = 9223372036854775807L;
    static final long LMIN = -9223372036854775808L;
    // util
    static int minof(int a, int b, int c) {return min(a, min(b, c));}
    static int minof(int... x) {if(x.length == 1) return x[0]; if(x.length == 2) return min(x[0], x[1]); if(x.length == 3) return min(x[0], min(x[1], x[2])); int min = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] < min) min = x[i]; return min;}
    static long minof(long a, long b, long c) {return min(a, min(b, c));}
    static long minof(long... x) {if(x.length == 1) return x[0]; if(x.length == 2) return min(x[0], x[1]); if(x.length == 3) return min(x[0], min(x[1], x[2])); long min = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] < min) min = x[i]; return min;}
    static int maxof(int a, int b, int c) {return max(a, max(b, c));}
    static int maxof(int... x) {if(x.length == 1) return x[0]; if(x.length == 2) return max(x[0], x[1]); if(x.length == 3) return max(x[0], max(x[1], x[2])); int max = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] > max) max = x[i]; return max;}
    static long maxof(long a, long b, long c) {return max(a, max(b, c));}
    static long maxof(long... x) {if(x.length == 1) return x[0]; if(x.length == 2) return max(x[0], x[1]); if(x.length == 3) return max(x[0], max(x[1], x[2])); long max = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] > max) max = x[i]; return max;}
    static int powi(int a, int b) {if(a == 0) return 0; int ans = 1; while(b > 0) {if((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static long powl(long a, int b) {if(a == 0) return 0; long ans = 1; while(b > 0) {if((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static int floori(double d) {return (int)d;}
    static int ceili(double d) {return (int)ceil(d);}
    static long floorl(double d) {return (long)d;}
    static long ceill(double d) {return (long)ceil(d);}
    static void reverse(int[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {int swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(long[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {long swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(double[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {double swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(char[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {char swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static <T> void reverse(T[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {T swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void shuffle(int[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); int swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(long[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); long swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(double[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); double swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(char[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); char swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static <T> void shuffle(T[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); T swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void rsort(int[] a) {shuffle(a); Arrays.sort(a);}
    static void rsort(long[] a) {shuffle(a); Arrays.sort(a);}
    static void rsort(double[] a) {shuffle(a); Arrays.sort(a);}
    static void rsort(char[] a) {shuffle(a); Arrays.sort(a);}
    static <T> void rsort(T[] a) {shuffle(a); Arrays.sort(a);}
    static int randInt(int min, int max) {return rand.nextInt(max - min + 1) + min;}
    // input
    static void r() throws IOException {input = new StringTokenizer(__in.readLine());}
    static int ri() throws IOException {return Integer.parseInt(__in.readLine());}
    static long rl() throws IOException {return Long.parseLong(__in.readLine());}
    static int[] ria(int n) throws IOException {int[] a = new int[n]; input = new StringTokenizer(__in.readLine()); for(int i = 0; i < n; ++i) a[i] = Integer.parseInt(input.nextToken()); return a;}
    static long[] rla(int n) throws IOException {long[] a = new long[n]; input = new StringTokenizer(__in.readLine()); for(int i = 0; i < n; ++i) a[i] = Long.parseLong(input.nextToken()); return a;}
    static char[] rcha() throws IOException {return __in.readLine().toCharArray();}
    static String rline() throws IOException {return __in.readLine();}
    static int rni() throws IOException {input = new StringTokenizer(__in.readLine()); return Integer.parseInt(input.nextToken());}
    static int ni() {return Integer.parseInt(input.nextToken());}
    static long rnl() throws IOException {input = new StringTokenizer(__in.readLine()); return Long.parseLong(input.nextToken());}
    static long nl() {return Long.parseLong(input.nextToken());}
    // output
    static void pr(int i) {__out.print(i);}
    static void prln(int i) {__out.println(i);}
    static void pr(long l) {__out.print(l);}
    static void prln(long l) {__out.println(l);}
    static void pr(double d) {__out.print(d);}
    static void prln(double d) {__out.println(d);}
    static void pr(char c) {__out.print(c);}
    static void prln(char c) {__out.println(c);}
    static void pr(char[] s) {__out.print(new String(s));}
    static void prln(char[] s) {__out.println(new String(s));}
    static void pr(String s) {__out.print(s);}
    static void prln(String s) {__out.println(s);}
    static void pr(Object o) {__out.print(o);}
    static void prln(Object o) {__out.println(o);}
    static void prln() {__out.println();}
    static void pryes() {__out.println("yes");}
    static void pry() {__out.println("Yes");}
    static void prY() {__out.println("YES");}
    static void prno() {__out.println("no");}
    static void prn() {__out.println("No");}
    static void prN() {__out.println("NO");}
    static void pryesno(boolean b) {__out.println(b ? "yes" : "no");};
    static void pryn(boolean b) {__out.println(b ? "Yes" : "No");}
    static void prYN(boolean b) {__out.println(b ? "YES" : "NO");}
    static void prln(int... a) {for(int i = 0, len = a.length - 1; i < len; __out.print(a[i]), __out.print(' '), ++i); __out.println(a[a.length - 1]);}
    static void prln(long... a) {for(int i = 0, len = a.length - 1; i < len; __out.print(a[i]), __out.print(' '), ++i); __out.println(a[a.length - 1]);}
    static <T> void prln(Collection<T> c) {int n = c.size() - 1; Iterator<T> iter = c.iterator(); for(int i = 0; i < n; __out.print(iter.next()), __out.print(' '), ++i); if(n >= 0) __out.println(iter.next());}
    static void h() {__out.println("hlfd");}
    static void flush() {__out.flush();}
    static void close() {__out.close();}
}