#include <bits/stdc++.h>
template <typename T>
std::ostream &operator<<(std::ostream &os, std::vector<T> v) {
  os << "[";
  for (int i = 0; i < int((v).size()); i++) os << v[i] << " ";
  return os << "]";
}
using namespace std;
long long INF = (1ll << 61);
vector<set<pair<long long, long long> > > tw;
int ins(set<pair<long long, long long> > &s, pair<long long, long long> &p) {
  int a = p.first;
  int del = 0;
  auto it = s.lower_bound({a, INF});
  if (it != s.begin()) {
    it--;
    if (it->second == a - 1) {
      p.first = it->first;
      s.erase(it);
      del++;
    }
  }
  int b = p.second;
  it = s.lower_bound({b, INF});
  if (it != s.end()) {
    if (it->first == b + 1) {
      p.second = it->second;
      s.erase(it);
      del++;
    }
  }
  s.insert(p);
  return del;
}
set<pair<long long, long long> > merge(set<pair<long long, long long> > &s1,
                                       set<pair<long long, long long> > &s2,
                                       long long &diff) {
  if (int((s1).size()) > int((s2).size())) {
    swap(s1, s2);
  }
  for (auto k : s1) {
    int del = ins(s2, k);
    diff -= del;
  }
  return std::move(s2);
}
int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<vector<long long> > v(m + 1);
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    v[a].push_back(i + 1);
  }
  tw.resize(m + 1);
  for (int k = 1; k < m + 1; k++) {
    sort(v[k].begin(), v[k].end());
    int i = 0;
    while (i < int((v[k]).size())) {
      int j = i;
      while (j < int((v[k]).size()) && v[k][j] == v[k][i] + (j - i)) {
        j++;
      }
      tw[k].insert({v[k][i], v[k][i] + (j - i - 1)});
      i = j;
    }
  }
  long long diff = 0;
  for (int i = 1; i < m + 1; i++) diff += int((tw[i]).size());
  cout << diff - 1 << '\n';
  for (int i = 0; i < m - 1; i++) {
    int a, b;
    cin >> a >> b;
    int target = a;
    tw[target] = merge(tw[a], tw[b], diff);
    cout << diff - 1 << '\n';
  }
  return 0;
}
