#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
cin>>n>>m;
vector<int> a(n), occ(m+1);
vector<vector<pair<int, int>>> col(m+1);
vector<pair<int, int>> best;
for(int i=0; i<n; ++i) {
cin>>a[i];
occ[a[i]]++;
if(i==0 || a[i] != a[i-1]) {
col[a[i]].push_back({i, i});
}
else {
col[a[i]].back().nd = i;
}
}
for(int i=1; i<=m; ++i) {
best.push_back({occ[i], i});
}
sort(best.rbegin(), best.rend());
vector<vector<int>> cnt(2, vector<int>(m+1));
for(int c=1; c<=m; ++c) {
if(col[c].empty()) continue;
vector<int> prv(2);
vector<bool> fail(2);
int beg = col[c][0].st;
int end = col[c][0].nd;
if(end==n-1) {
int ans = n;
for(int i=0; i<min(m, 2); ++i) {
if(c==best[i].nd) ans=min(ans, n-occ[c]);
else ans = min(ans, n-occ[c]-occ[best[i].nd]);
}
cout<<ans<<'\n';
continue;
}
if((end-beg+1)%2==1) {
if(beg==0) {
prv[0] = end;
cnt[1][a[end+1]] = 1;
prv[1] = end+1;
}
else {
cnt[0][a[beg-1]] = 1;
prv[0] = end;
cnt[1][a[end+1]] = 1;
prv[1] = end+1;
}
}
else {
if(beg==0) {
prv[0] = end;
cnt[1][a[end+1]] = 1;
prv[1] = end+1;
}
else {
prv[0] = end;
cnt[1][a[beg-1]] = 1;
cnt[1][a[end+1]] = 1;
prv[1] = end+1;
}
}
for(int it=0; it<=1; ++it) {
bool start=0;
for(auto cur: col[c]) {
if(!start) {
start=1;
continue;
}
beg = cur.st;
end = cur.nd;
if((beg-prv[it])%2==0) {
beg--;
cnt[it][a[beg]]++;
}
if((end-beg+1)%2==1 && end != n-1) {
end++;
cnt[it][a[end]]++;
}
prv[it] = end;
}
}
int ans = n;
for(int j=0; j<min(m, (int)col[c].size()+1); ++j) {
int i = best[j].nd;
if(c==i) {
ans = min(ans, n-occ[c]);
}
else {
if(!fail[0]) ans = min(ans, n - occ[c] - occ[i] + cnt[0][i]);
if(!fail[1]) ans = min(ans, n - occ[c] - occ[i] + cnt[1][i]);
}
}
cout<<ans<<'\n';
for(auto i: col[c]) {
if(i.st != 0) cnt[0][a[i.st-1]]=cnt[1][a[i.st-1]]=0;
if(i.nd != n-1) cnt[0][a[i.nd+1]]=cnt[1][a[i.nd+1]]=0;
}
}
}
