#include "bits/stdc++.h"
#include <utility>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MAXN = 1000000;
const int MAXM = 1000000;
int n, m;
int a[MAXN + 5];
vector<int> v[MAXM + 5];
int pairing[MAXN + 5];
int ans[MAXM + 5];
int cnt[MAXM + 5];
int cntOcc[MAXN + 5];
int mx;
void del(int x) {
--cntOcc[cnt[x]];
if (cntOcc[cnt[x]] == 0 && mx == cnt[x]) --mx;
++cntOcc[--cnt[x]];
}
void ins(int x) {
--cntOcc[cnt[x]];
if (mx == cnt[x]) ++mx;
++cntOcc[++cnt[x]];
}
void solve() {
// for (int j = 1; j <= m; j++) {
// cout << "@@" << j << " " << cnt[j] << endl;
// }
// for (int j = 1; j <= n; j++) {
// cout << "!@# " << j << " " << cntOcc[j] << endl;
// }
// cout << "@@" << mx << endl;
for (int i = 1; i <= m; i++) {
int oricol = cnt[i];
for (int j = 1; j <= oricol; j++) {
del(i);
}
for (int x : v[i]) {
if (pairing[x] != 0 && a[pairing[x]] != a[x]) {
del(a[pairing[x]]);
}
}
// for (int j = 1; j <= m; j++) {
// cout << "##" << j << " " << cnt[j] << endl;
// }
ans[i] = min(ans[i], n - oricol - mx);
// cout << "!!!" << i << " " << mx << " " << ans[i] << endl;
for (int x : v[i]) {
if (pairing[x] != 0 && a[pairing[x]] != a[x]) {
ins(a[pairing[x]]);
}
}
for (int j = 1; j <= oricol; j++) {
ins(i);
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
if (m == 1) {
cout << "0\n";
return 0;
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
v[a[i]].push_back(i);
++cnt[a[i]];
}
for (int i = 1; i <= m; i++) {
ans[i] = 1e9;
++cntOcc[cnt[i]];
mx = max(mx, cnt[i]);
}
for (int i = 1; i <= n; i += 2) {
if (i == n) {
pairing[i] = 0;
}
else {
pairing[i] = i + 1;
pairing[i + 1] = i;
}
}
solve();
pairing[1] = 0;
for (int i = 2; i <= n; i += 2) {
if (i == n) {
pairing[i] = 0;
}
else {
pairing[i] = i + 1;
pairing[i + 1] = i;
}
}
solve();
for (int i = 1; i <= m; i++) {
cout << ans[i] << "\n";
}
}
