#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e6+5;
int n, m;
int a[mxn], ans[mxn];
int mxcnt = 0;
int cnt[mxn], revcnt[mxn];
vector<vector<int>> where;
void add(int x) {
if(cnt[x] == mxcnt) mxcnt++;
revcnt[cnt[x]]--;
cnt[x]++;
revcnt[cnt[x]]++;
}
void rem(int x) {
if(cnt[x] == mxcnt && revcnt[cnt[x]] == 1) mxcnt--;
revcnt[cnt[x]]--;
cnt[x]--;
revcnt[cnt[x]]++;
}
int main(int argc, char const *argv[]) {
cin >> n >> m;
where.resize(m+1);
for(int i = 0; i < n; i++) cin >> a[i], where[a[i]].push_back(i);
for(int i = 1; i <= m; i++) ans[i] = n;
int curr = n;
for(int i = 0; i < n; i++) add(a[i]);
for(int skipfirst : {1, 0}) {
for(int i = 1; i <= m; i++) {
for(int j : where[i]) {
curr--; rem(a[j]);
if(j % 2 == skipfirst) {
// from left
if(j == n-1) continue; // not part of a pair
if(a[j+1] != i) rem(a[j+1]);
}
else {
// from right
if(j == 0) continue; // not part of a pair
if(a[j-1] != i) rem(a[j-1]);
}
}
ans[i] = min(ans[i], curr-mxcnt);
for(int j : where[i]) {
curr++; add(a[j]);
if(j % 2 == skipfirst) {
// from left
if(j == n-1) continue; // not part of a pair
if(a[j+1] != i) add(a[j+1]);
}
else {
// from right
if(j == 0) continue; // not part of a pair
if(a[j-1] != i) add(a[j-1]);
}
}
}
}
for(int i = 1; i <= m; i++) {
cout << ans[i] << "\n";
}
return 0;
}
