#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MAX_N = 1e6+7;
constexpr int MAX_M = 5e3+7;
int N; // liczba węzłów
int M; // liczba kolorów
int C[MAX_N];
int ans[MAX_M];
int cnt_color[MAX_M];
int M_1[MAX_M][MAX_M];
int M_2[MAX_M][MAX_M];
int with_one_1[MAX_M];
int with_one_2[MAX_M];
int with_any_1[MAX_M];
int with_any_2[MAX_M];
int cnt_pairs_1 = 0;
int cnt_pairs_2 = 0;
int last1 = 0;
int first2 = 0;
int last2 = 0;
int cost(int a, int b) {
int pairs_ab_1 = M_1[a][b];
int cost1 = with_one_1[a] + with_one_1[b] - pairs_ab_1 + 2 * (cnt_pairs_1 - with_any_1[a] - with_any_1[b] + pairs_ab_1) + (last1 != a && last1 != b && last1 != 0);
int pairs_ab_2 = M_2[a][b];
int cost2 = with_one_2[a] + with_one_2[b] - pairs_ab_2 + 2 * (cnt_pairs_2 - with_any_2[a] - with_any_2[b] + pairs_ab_2) + (first2 != a && first2 != b && first2 != 0) + (last2 != a && last2 != b && last2 != 0);
return min(cost1, cost2);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M;
for (int i=1; i<=N; i++) {
cin >> C[i];
cnt_color[C[i]]++;
}
for (int i=1; i<=M; i++) ans[i] = N - cnt_color[i];
for (int i=1; i+1<=N; i+=2) {
M_1[C[i]][C[i+1]]++;
M_1[C[i+1]][C[i]]++;
cnt_pairs_1++;
if (C[i] == C[i+1]) with_any_1[C[i]]++;
else with_one_1[C[i]]++, with_one_1[C[i+1]]++, with_any_1[C[i]]++, with_any_1[C[i+1]]++;
}
if (N % 2 == 1) last1 = C[N];
first2 = C[1];
for (int i=2; i+1<=N; i+=2) {
M_2[C[i]][C[i+1]]++;
M_2[C[i+1]][C[i]]++;
cnt_pairs_2++;
if (C[i] == C[i+1]) with_any_2[C[i]] ++;
else with_one_2[C[i]]++, with_one_2[C[i+1]]++, with_any_2[C[i]]++, with_any_2[C[i+1]]++;
}
if (N % 2 == 0) last2 = C[N];
for (int i=1; i<=M-1; i++) for (int j=i+1; j<=M; j++) {
int temp = cost(i,j);
ans[i] = min(ans[i], temp);
ans[j] = min(ans[j], temp);
}
for (int i=1; i<=M; i++) cout << ans[i] << '\n';
}
