#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1000000;
const int N_ = 1 << 20;
int aa[N], st[N_ << 1], n_, ans[N];
vector<int> ii[N];
void pul(int i) {
int l = i << 1, r = l ^ 1;
st[i] = min(st[l], st[r]);
}
void build(int n) {
for (n_ = 1; n_ < n; n_ <<= 1)
;
for (int i = 0; i < n_; i++)
st[i + n_] = 0;
for (int i = n_ - 1; i; i--)
pul(i);
}
void update(int i, int a) {
st[i += n_] += a;
while (i >>= 1)
pul(i);
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int n, a_; cin >> n >> a_;
for (int i = 0; i < n; i++)
cin >> aa[i], aa[i]--;
for (int a = 0; a < a_; a++)
ans[a] = n;
for (int i_ = 0; i_ < 2; i_++) {
build(a_);
for (int a = 0; a < a_; a++)
ii[a].clear();
int s = 0;
for (int i = i_; i <= n; i += 2) {
if (i < n) {
int a = aa[i];
s++, update(a, -1);
ii[a].push_back(i);
}
if (i) {
int a = aa[i - 1];
s++, update(a, -1);
if (i == n || a != aa[i])
ii[a].push_back(i);
}
}
for (int a = 0; a < a_; a++) {
int x = 0;
for (int i : ii[a]) {
if (i && i < n && aa[i] != aa[i - 1])
x++;
if (i < n) {
int a = aa[i];
s--, update(a, 1);
}
if (i) {
int a = aa[i - 1];
s--, update(a, 1);
}
}
ans[a] = min(ans[a], x + s + st[1]);
for (int i : ii[a]) {
if (i < n) {
int a = aa[i];
s++, update(a, -1);
}
if (i) {
int a = aa[i - 1];
s++, update(a, -1);
}
}
}
}
for (int a = 0; a < a_; a++)
cout << ans[a] << '\n';
return 0;
}
