#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 1;
int n, m, c[N], mn[N];
vector <int> occ[N];
void solve () {
cin >> n >> m;
if (m == 1) {
cout << 0 << '\n';
return;
}
for (int i = 1; i <= n; i++) {
cin >> c[i];
occ[c[i]].push_back(i);
}
for (int i = 1; i <= m; i++) {
mn[i] = 1e9;
}
if (n % 2 == 1) {
vector <int> ff(m + 1, 0);
for (int i = 1; i <= n; i++) {
ff[c[i]]++;
}
set <pair <int, int>> mxs;
for (int i = 1; i <= m; i++) {
mxs.insert({ff[i], i});
}
for (int i = 1; i <= m; i++) {
mxs.erase({ff[i], i});
int s = n, v = 0;
for (auto j : occ[i]) {
if (j % 2 == 1) {
if (j + 1 <= n) {
if (c[j + 1] != i) {
v++;
mxs.erase({ff[c[j + 1]], c[j + 1]});
ff[c[j + 1]]--;
mxs.insert({ff[c[j + 1]], c[j + 1]});
}
}
if (j == n) {
s--;
} else {
s -= 2;
}
} else {
if (c[j - 1] != i) {
v++;
mxs.erase({ff[c[j - 1]], c[j - 1]});
ff[c[j - 1]]--;
mxs.insert({ff[c[j - 1]], c[j - 1]});
s -= 2;
}
}
}
assert(!mxs.empty());
mn[i] = min(mn[i], v + s - (*(--mxs.end())).first);
for (auto j : occ[i]) {
if (j % 2 == 1) {
if (j + 1 <= n) {
if (c[j + 1] != i) {
mxs.erase({ff[c[j + 1]], c[j + 1]});
ff[c[j + 1]]++;
mxs.insert({ff[c[j + 1]], c[j + 1]});
}
}
} else {
if (c[j - 1] != i) {
mxs.erase({ff[c[j - 1]], c[j - 1]});
ff[c[j - 1]]++;
mxs.insert({ff[c[j - 1]], c[j - 1]});
}
}
}
mxs.insert({ff[i], i});
}
}
if (n % 2 == 1) {
vector <int> ff(m + 1, 0);
for (int i = 1; i <= n; i++) {
ff[c[i]]++;
}
set <pair <int, int>> mxs;
for (int i = 1; i <= m; i++) {
mxs.insert({ff[i], i});
}
for (int i = 1; i <= m; i++) {
mxs.erase({ff[i], i});
int s = n, v = 0;
for (auto j : occ[i]) {
if (j % 2 == 0) {
if (c[j + 1] != i) {
v++;
mxs.erase({ff[c[j + 1]], c[j + 1]});
ff[c[j + 1]]--;
mxs.insert({ff[c[j + 1]], c[j + 1]});
}
s -= 2;
} else {
if (j > 1) {
if (c[j - 1] != i) {
v++;
mxs.erase({ff[c[j - 1]], c[j - 1]});
ff[c[j - 1]]--;
mxs.insert({ff[c[j - 1]], c[j - 1]});
s -= 2;
}
} else {
s--;
}
}
}
assert(!mxs.empty());
mn[i] = min(mn[i], v + s - (*(--mxs.end())).first);
for (auto j : occ[i]) {
if (j % 2 == 0) {
if (c[j + 1] != i) {
mxs.erase({ff[c[j + 1]], c[j + 1]});
ff[c[j + 1]]++;
mxs.insert({ff[c[j + 1]], c[j + 1]});
}
} else {
if (j > 1) {
if (c[j - 1] != i) {
mxs.erase({ff[c[j - 1]], c[j - 1]});
ff[c[j - 1]]++;
mxs.insert({ff[c[j - 1]], c[j - 1]});
}
}
}
}
mxs.insert({ff[i], i});
}
}
if (n % 2 == 0) {
vector <int> ff(m + 1, 0);
for (int i = 1; i <= n; i++) {
ff[c[i]]++;
}
set <pair <int, int>> mxs;
for (int i = 1; i <= m; i++) {
mxs.insert({ff[i], i});
}
for (int i = 1; i <= m; i++) {
mxs.erase({ff[i], i});
int s = n, v = 0;
for (auto j : occ[i]) {
if (j % 2 == 1) {
if (c[j + 1] != i) {
v++;
mxs.erase({ff[c[j + 1]], c[j + 1]});
ff[c[j + 1]]--;
mxs.insert({ff[c[j + 1]], c[j + 1]});
}
s -= 2;
} else {
if (c[j - 1] != i) {
v++;
mxs.erase({ff[c[j - 1]], c[j - 1]});
ff[c[j - 1]]--;
mxs.insert({ff[c[j - 1]], c[j - 1]});
s -= 2;
}
}
}
assert(!mxs.empty());
mn[i] = min(mn[i], v + s - (*(--mxs.end())).first);
for (auto j : occ[i]) {
if (j % 2 == 1) {
if (c[j + 1] != i) {
mxs.erase({ff[c[j + 1]], c[j + 1]});
ff[c[j + 1]]++;
mxs.insert({ff[c[j + 1]], c[j + 1]});
}
} else {
if (c[j - 1] != i) {
mxs.erase({ff[c[j - 1]], c[j - 1]});
ff[c[j - 1]]++;
mxs.insert({ff[c[j - 1]], c[j - 1]});
}
}
}
mxs.insert({ff[i], i});
}
}
if (n % 2 == 0) {
vector <int> ff(m + 1, 0);
for (int i = 1; i <= n; i++) {
ff[c[i]]++;
}
set <pair <int, int>> mxs;
for (int i = 1; i <= m; i++) {
mxs.insert({ff[i], i});
}
for (int i = 1; i <= m; i++) {
mxs.erase({ff[i], i});
int s = n, v = 0;
for (auto j : occ[i]) {
if (j % 2 == 0) {
if (j == n) {
s--; continue;
}
if (c[j + 1] != i) {
v++;
mxs.erase({ff[c[j + 1]], c[j + 1]});
ff[c[j + 1]]--;
mxs.insert({ff[c[j + 1]], c[j + 1]});
}
s -= 2;
} else {
if (j == 1) {
s--; continue;
}
if (c[j - 1] != i) {
v++;
mxs.erase({ff[c[j - 1]], c[j - 1]});
ff[c[j - 1]]--;
mxs.insert({ff[c[j - 1]], c[j - 1]});
s -= 2;
}
}
}
assert(!mxs.empty());
mn[i] = min(mn[i], v + s - (*(--mxs.end())).first);
for (auto j : occ[i]) {
if (j % 2 == 0) {
if (j == n) {
s--; continue;
}
if (c[j + 1] != i) {
v++;
mxs.erase({ff[c[j + 1]], c[j + 1]});
ff[c[j + 1]]++;
mxs.insert({ff[c[j + 1]], c[j + 1]});
}
s -= 2;
} else {
if (j == 1) {
s--; continue;
}
if (c[j - 1] != i) {
v++;
mxs.erase({ff[c[j - 1]], c[j - 1]});
ff[c[j - 1]]++;
mxs.insert({ff[c[j - 1]], c[j - 1]});
s -= 2;
}
}
}
mxs.insert({ff[i], i});
}
}
for (int i = 1; i <= m; i++) {
cout << mn[i] << '\n';
}
}
signed main () {
ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
