#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 1e6 + 5;
int n, m;
int c[N], res[N], cnt[N], s[4 * N];
vector<int> g[N];
void bld(int id = 1, int l = 1, int r = m) {
if (l == r) {
s[id] = cnt[l];
return;
}
int md = (l + r) / 2;
bld(id * 2, l, md);
bld(id * 2 + 1, md + 1, r);
s[id] = max(s[id * 2], s[id * 2 + 1]);
}
void upd(int i, int x, int id = 1, int l = 1, int r = m) {
if (l == r) {
s[id] += x;
return;
}
int md = (l + r) / 2;
if (i <= md) {
upd(i, x, id * 2, l, md);
} else {
upd(i, x, id * 2 + 1, md + 1, r);
}
s[id] = max(s[id * 2], s[id * 2 + 1]);
}
void add(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
void solve(int p) {
for (int i = 1; i <= m; ++i) {
g[i].clear();
}
bld();
for (int i = p; i + 1 <= n; i += 2) {
if (c[i] != c[i + 1]) {
add(c[i], c[i + 1]);
}
}
for (int i = 1; i <= m; ++i) {
upd(i, -cnt[i]);
for (int j : g[i]) {
upd(j, -1);
}
res[i] = max(res[i], cnt[i] + s[1]);
for (int j : g[i]) {
upd(j, 1);
}
upd(i, cnt[i]);
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> c[i];
++cnt[c[i]];
}
solve(1);
solve(2);
for (int i = 1; i <= m; ++i) {
cout << n - res[i] << "\n";
}
return 0;
}
