//
// Created by 42kangaroo on 11/09/2023.
//
#include "bits/stdc++.h"
using namespace std;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, c; cin >> n >> c;
vector<int> colorNum(c);
// count number of each color, and adjacent pairs of odd/even
// put these pairs into a vec<vec<int>>
vector<unordered_map<int,int>> adjO(c);
vector<unordered_map<int,int>> adjE(c);
int last = -1;
for (int i = 0; i < n; ++i) {
int a; cin >> a;
--a;
colorNum[a]++;
if (last != -1 && last != a) {
if (i%2) {adjO[last][a]++; adjO[a][last]++;}
else {adjE[last][a]++; adjE[a][last]++;}
}
last = a;
}
// and sort it afterwards by num
vector<int> o(c);
std::iota(o.begin(), o.end(),0);
std::sort(o.begin(), o.end(), [&](int l, int r){return colorNum[l] > colorNum[r];});
// take max of both(odd/even) for each
vector<unordered_map<int,int>> mins(c);
for (int i = 0; i < c; ++i) {
for (auto [k, v]: adjE[i]) {
if (adjO[i].find(k) != adjO[i].end()) {
mins[i][k] = min(adjO[i][k], adjE[i][k]);
}
}
}
// go down with a pointer in the sorted list and check those with connection the max without
for (int i = 0; i < c; ++i) {
int mi = n - colorNum[i];
int j = 0;
if (j < c && o[j] == i) j++;
for (; j < c && mins[i].find(o[j]) != mins[i].end(); ++j) {
mi = min(n - colorNum[i] - colorNum[o[j]] + mins[i][o[j]], mi);
if (j < c - 1 && o[j + 1] == i) ++j;
}
if (j < c) {
mi = min(n - colorNum[i] - colorNum[o[j]], mi);
}
cout << mi<< "\n";
}
}
