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.*;
 
public class Main extends PrintWriter {
    
    
    class Interval implements Comparable<Interval>{
        
        int l;
        int r;
        
        public Interval(int l, int r) {
            this.l = l;
            this.r = r;            
        }

        @Override
        public int compareTo(Interval arg0) {
            return Integer.compare(l, arg0.l);
        }
        
    }
    
    private void solve() {       
        int n = sc.nextInt();
        int m = sc.nextInt();
        AVLTree<Interval>[] towers = new AVLTree[m];
        for(int i = 0; i < m; i++) towers[i] = new AVLTree<>();
        for(int i = 0; i < n; i++) {
            insert(towers[sc.nextInt()-1], new Interval(i,i));
        }
        int sum = 0;
        for(int i = 0; i < m; i++) {
            sum += towers[i].count;
        }
        println(sum-1);
        for(int q = 0; q < m-1; q++) {
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            sum -= towers[a].count;
            sum -= towers[b].count;
            AVLTree<Interval> a_ = towers[a];
            AVLTree<Interval> b_ = towers[b];
            if(a_.count < b_.count) {
                AVLTree<Interval> temp = a_;
                a_ = b_;
                b_ = temp;
            }
            navigateAndInsert(a_, b_.root);
            towers[a] = a_;
            sum += towers[a].count;
            println(sum-1);
        }
        

    }
    
    void navigateAndInsert(AVLTree<Interval> other, TreeNode<Interval> node) {
        if(node == null) return;
        insert(other, node.data);
        navigateAndInsert(other, node.left);
        navigateAndInsert(other, node.right);
    }
    
    void insert(AVLTree<Interval> set, Interval add) {
        Interval lower = set.findLessOrEqualTo(add);
        if(lower != null && lower.r == add.l-1) {
            set.remove(lower);
            add.l = lower.l;
        }
        
        
        Interval higher = set.findGreaterOrEqualTo(add);
        if(higher != null && higher.l == add.r+1) {
            set.remove(higher);
            add.r = higher.r;
        }

        set.insert(add);
    }
    
    
    
//  Solution() throws FileNotFoundException { super(new File("output.txt")); }
//  InputReader sc = new InputReader(new FileInputStream("test_input.txt"));
    
  Main() { super(System.out); }
  InputReader sc = new InputReader(System.in);
  static class InputReader {
      InputReader(InputStream in) { this.in = in; } InputStream in;
      
      private byte[] buf = new byte[16384];
      private int    curChar;
      private int    numChars;
      
 
      public int read() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = in.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextLine() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          StringBuilder res = new StringBuilder();
          do {
              res.appendCodePoint(c);
              c = read();
          } while (!isEndOfLine(c));
          return res.toString();
      }
 
      public String nextString() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          StringBuilder res = new StringBuilder();
          do {
              res.appendCodePoint(c);
              c = read();
          } while (!isSpaceChar(c));
          return res.toString();
      }
 
      public long nextLong() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = read();
          }
          long res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = read();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public int nextInt() {
          int c = read();
          while (isSpaceChar(c))
              c = read();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = read();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = read();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      private boolean isSpaceChar(int c) {
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      private boolean isEndOfLine(int c) {
          return c == '\n' || c == '\r' || c == -1;
      }
  }
 
    public static void main(String[] $) {
        new Thread(null, new Runnable() {
            public void run() {
                long start = System.nanoTime();
                try {Main solution = new Main(); solution.solve(); solution.close();} 
                catch (Exception e) {e.printStackTrace(); System.exit(1);}
                System.err.println((System.nanoTime()-start)/1E9);
            }
        }, "1", 1 << 27).start();
 
    }
 class AVLTree<E extends Comparable<E>> {
        
        TreeNode<E> root;
        
        int count = 0;
        
        public E findGreaterOrEqualTo(E data) {
            return this.findGreaterOrEqualTo(root, data);
        }
        
        private E findGreaterOrEqualTo(TreeNode<E> node, E data){
            E res = null;
            if(node == null) return res;
            if(data.compareTo(node.data) < 0) {
                res = node.data;
                if(data.compareTo(node.data) < 0) {
                    E comp = findGreaterOrEqualTo(node.left, data);
                    if(comp != null) res = comp; 
                }
            }else {

                res = findGreaterOrEqualTo(node.right, data);
            }
            return res;
        }
        
        public E findLessOrEqualTo(E data) {
            return this.findLessOrEqualTo(root, data);
        }
        
        private E findLessOrEqualTo(TreeNode<E> node, E data){
            E res = null;
            if(node == null) return res;
            if(data.compareTo(node.data) < 0) {
                res = findLessOrEqualTo(node.left, data);
            }else {
                res = node.data;
                if(data.compareTo(node.data) > 0) {
                    E comp = findLessOrEqualTo(node.right, data);
                    if(comp != null) res = comp; 
                }
            }
            return res;
        }
        
        
        public void insert(E data) {
            count++;
            root = insert(root, data);
        }
        
        private TreeNode<E> insert(TreeNode<E> node, E data){
            if(node == null) {
                node = new TreeNode<E>(data);
            }else {
                if(data.compareTo(node.data) <= 0) {
                    node.left = insert(node.left, data);
                }else if(data.compareTo(node.data) > 0) {
                    node.right = insert(node.right, data);
                }
                 
            }
            node = checkAVL(node);
            return node;
        }
        
        public void remove(E key) {
            count--;
            root = remove(root, key);
        }
        
        private TreeNode<E> remove(TreeNode<E> node, E data){
            if(data.compareTo(node.data) < 0){
                node.left = remove(node.left, data);
            }else if(data.compareTo(node.data) > 0){
                node.right = remove(node.right, data);
            }else {
                if(node.left == null && node.right == null) {
                    node = null;
                }else if(node.left == null) {
                    node = node.right;
                }else if(node.right == null) {
                    node = node.left;
                }else{
                    node.right = minimum(node.right);
                    node.data = successor;
                }
            }
            node = (node != null)? checkAVL(node) : node;
            return node;
        }
        
 
        E successor;
        
        TreeNode<E> minimum(TreeNode<E> node) {
            if(node.left == null) {
                successor = node.data;
                node = node.right;
            }else {
                node.left = minimum(node.left);
                node = checkAVL(node);
            }
            return node;
        }
 
        private TreeNode<E> checkAVL(TreeNode<E> node){
            if(node != null) {
                int balance = getBalance(node);
                if(balance < -1 || balance > 1){
                    node = rotate(node, balance);
                }
                update(node);
            }
            return node;
        }
 
        private TreeNode<E> rotate(TreeNode<E> node, int balance){
            if(balance < -1) {
                if(getBalance(node.left) <= 0) {
                    node = rotateLeftLeft(node);
                }else {
                    node = rotateLeftRight(node);
                }
            }else {
                if(getBalance(node.right) >= 0) {
                    node = rotateRightRight(node);
                }else {
                    node = rotateRightLeft(node);
                }
            }
            return node;
        }
        
        private TreeNode<E> rotateRightLeft(TreeNode<E> node) {
            TreeNode<E> pivot = node.right;
            TreeNode<E> root = pivot.left;
            pivot.left = root.right;
            node.right = root.left;
            root.right = pivot;
            root.left = node;
            update(pivot);
            update(node);
            return root;
        }
 
        private TreeNode<E> rotateRightRight(TreeNode<E> node) {
            TreeNode<E> root = node.right;
            node.right = root.left;
            root.left = node;
            update(node);
            return root;
        }
 
        private TreeNode<E> rotateLeftRight(TreeNode<E> node) {
            TreeNode<E> pivot = node.left;
            TreeNode<E> root = pivot.right;
            pivot.right = root.left;
            node.left = root.right;
            root.left = pivot;
            root.right = node;
            update(pivot);
            update(node);
            return root;
        }
 
        private TreeNode<E> rotateLeftLeft(TreeNode<E> node) {
            TreeNode<E> root = node.left;
            node.left = root.right;
            root.right = node;
            update(node);
            return root;
        }
        
        
        private void update(TreeNode<E> node) {
            if(node != null) {
                node.height = Math.max(getHeight(node.left), getHeight(node.right))+1;
            }
        }
 
        private int getBalance(TreeNode<E> node) {
            return getHeight(node.right) - getHeight(node.left);
        }
        
        private int getHeight(TreeNode<E> node) {
            return node != null? node.height : -1;
        }
        

        
       
        
            
    }
 
    class TreeNode<E extends Comparable<E>>{
        E data;
        int height;
        TreeNode<E> left;
        TreeNode<E> right;
        
        public TreeNode(E data){
            this.data = data;
        }
    }
 
}