#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1000000
#define M N
#define N_ (1 << 20) /* N_ = pow2(ceil(log2(M))) */
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int *ei[M], eo[M];
void append(int a, int i) {
int o = eo[a]++;
if (o >= 2 && (o & o - 1) == 0)
ei[a] = (int *) realloc(ei[a], o * 2 * sizeof *ei[a]);
ei[a][o] = i;
}
int st[N_ * 2], n_;
void pul(int i) {
st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}
void update(int i, int x) {
st[i += n_] += x;
while (i > 1)
pul(i >>= 1);
}
int main() {
static int aa[N], ans[M];
int n, m, r, i, a, o, ka, kb;
scanf("%d%d", &n, &m);
if (m == 1) {
printf("0\n");
return 0;
}
for (a = 0; a < n; a++)
ei[a] = (int *) malloc(2 * sizeof *ei[a]);
for (i = 0; i < n; i++) {
scanf("%d", &aa[i]), aa[i]--;
append(aa[i], i);
}
n_ = 1;
while (n_ < m)
n_ <<= 1;
for (i = 0; i < n; i++)
update(aa[i], 1);
memset(ans, 0x3f, n * sizeof *ans);
for (r = 0; r < 2; r++)
for (a = 0; a < m; a++) {
ka = st[n_ + a];
for (o = eo[a]; o--; ) {
i = ei[a][o];
update(aa[i], -1);
if (i % 2 == r) {
if (i > 0)
update(aa[i - 1], -1);
} else {
if (i + 1 < n)
update(aa[i + 1], -1);
}
}
kb = st[1];
ans[a] = min(ans[a], n - ka - kb);
for (o = eo[a]; o--; ) {
i = ei[a][o];
update(aa[i], 1);
if (i % 2 == r) {
if (i > 0)
update(aa[i - 1], 1);
} else {
if (i + 1 < n)
update(aa[i + 1], 1);
}
}
}
for (a = 0; a < m; a++)
printf("%d\n", ans[a]);
return 0;
}
