#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];
#define mid ((l + r) >> 1)
int tree[N << 2], leaf[N];
void init (int l, int r, int node) {
if (l == r) {
leaf[l] = node;
} else {
init(l, mid, 2 * node); init(mid + 1, r, 2 * node + 1);
}
}
void update (int x, int y) {
int u = leaf[x];
tree[u] += y;
while (u > 1) {
u >>= 1;
tree[u] = max(tree[2 * u], tree[2 * u + 1]);
}
}
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;
}
init(1, m, 1);
vector <int> ff(m + 1, 0);
for (int i = 1; i <= n; i++) {
ff[c[i]]++;
}
if (n % 2 == 1) {
memset(tree, 0, sizeof(tree));
for (int i = 1; i <= m; i++) {
update(i, ff[i]);
}
for (int i = 1; i <= m; i++) {
update(i, -ff[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++;
update(c[j + 1], -1);
}
}
if (j == n) {
s--;
} else {
s -= 2;
}
} else {
if (c[j - 1] != i) {
v++;
update(c[j - 1], -1);
s -= 2;
}
}
}
mn[i] = min(mn[i], v + s - tree[1]);
for (auto j : occ[i]) {
if (j % 2 == 1) {
if (j + 1 <= n) {
if (c[j + 1] != i) {
update(c[j + 1], 1);
}
}
} else {
if (c[j - 1] != i) {
update(c[j - 1], 1);
}
}
}
update(i, ff[i]);
}
}
if (n % 2 == 1) {
memset(tree, 0, sizeof(tree));
for (int i = 1; i <= m; i++) {
update(i, ff[i]);
}
for (int i = 1; i <= m; i++) {
update(i, -ff[i]);
int s = n, v = 0;
for (auto j : occ[i]) {
if (j % 2 == 0) {
if (c[j + 1] != i) {
v++;
update(c[j + 1], -1);
}
s -= 2;
} else {
if (j > 1) {
if (c[j - 1] != i) {
v++;
update(c[j - 1], -1);
s -= 2;
}
} else {
s--;
}
}
}
mn[i] = min(mn[i], v + s - tree[1]);
for (auto j : occ[i]) {
if (j % 2 == 0) {
if (c[j + 1] != i) {
update(c[j + 1], 1);
}
} else {
if (j > 1) {
if (c[j - 1] != i) {
update(c[j - 1], 1);
}
}
}
}
update(i, ff[i]);
}
}
if (n % 2 == 0) {
memset(tree, 0, sizeof(tree));
for (int i = 1; i <= m; i++) {
update(i, ff[i]);
}
for (int i = 1; i <= m; i++) {
update(i, -ff[i]);
int s = n, v = 0;
for (auto j : occ[i]) {
if (j % 2 == 1) {
if (c[j + 1] != i) {
v++;
update(c[j + 1], -1);
}
s -= 2;
} else {
if (c[j - 1] != i) {
v++;
update(c[j - 1], -1);
s -= 2;
}
}
}
mn[i] = min(mn[i], v + s - tree[1]);
for (auto j : occ[i]) {
if (j % 2 == 1) {
if (c[j + 1] != i) {
update(c[j + 1], 1);
}
} else {
if (c[j - 1] != i) {
update(c[j - 1], 1);
}
}
}
update(i, ff[i]);
}
}
if (n % 2 == 0) {
memset(tree, 0, sizeof(tree));
for (int i = 1; i <= m; i++) {
update(i, ff[i]);
}
for (int i = 1; i <= m; i++) {
update(i, -ff[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++;
update(c[j + 1], -1);
}
s -= 2;
} else {
if (j == 1) {
s--; continue;
}
if (c[j - 1] != i) {
v++;
update(c[j - 1], -1);
s -= 2;
}
}
}
mn[i] = min(mn[i], v + s - tree[1]);
for (auto j : occ[i]) {
if (j % 2 == 0) {
if (j == n) {
s--; continue;
}
if (c[j + 1] != i) {
v++;
update(c[j + 1], 1);
}
s -= 2;
} else {
if (j == 1) {
s--; continue;
}
if (c[j - 1] != i) {
v++;
update(c[j - 1], 1);
s -= 2;
}
}
}
update(i, ff[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();
}
