#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto a : (b))
#define repIn2(a, b, c) for(auto [a, b] : (c))
constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
#define int ll
using namespace std;
struct hsh {
ll operator() (pair<int, int> x) const {
ll a = x.first, b = x.second;
return (a << 32) | b;
}
};
constexpr int maxm = 1e6 + 7, maxTb = 1 << 20, maxLog = 20;
int n, m;
int iniCol[maxm];
int ans[maxm];
unordered_map<pair<int, int>, int, hsh> ileTakich;
int ilePojedynczych[maxm], ilePodwojnych[maxm];
unordered_map<pair<int, int>, int, hsh> ileTakich2;
int ilePojedynczych2[maxm], ilePodwojnych2[maxm];
basic_string<char32_t> skim[maxm];
pair<int, int> maxSuf[maxm];
pair<int, int> st[maxm][maxLog];
int tb;
void checkCols1(int c1, int c2) {
if(c1 > c2) swap(c1, c2);
int ileWsumie = n / 2;
auto ilePoj = ilePojedynczych[c1] + ilePojedynczych[c2] - ileTakich[pair{c1, c2}];
auto ilePod = ilePodwojnych[c1] + ilePodwojnych[c2];
auto cost1 = (ileWsumie - ilePod) * 2 - ilePoj;
if(n % 2 == 1) cost1 += iniCol[n - 1] != c1 && iniCol[n - 1] != c2;
if(n % 2 == 0) ileWsumie--;
ilePoj = ilePojedynczych2[c1] + ilePojedynczych2[c2] - ileTakich2[pair{c1, c2}];
ilePod = ilePodwojnych2[c1] + ilePodwojnych2[c2];
auto cost2 = (ileWsumie - ilePod) * 2 - ilePoj;
cost2 += iniCol[0] != c1 && iniCol[0] != c2;
if(n % 2 == 0) cost2 += iniCol[n - 1] != c1 && iniCol[n - 1] != c2;
auto cost = min(cost1, cost2);
ans[c1] = min(ans[c1], cost);
ans[c2] = min(ans[c2], cost);
}
void checkCols2(int c1, int c2) {
if(c1 > c2) swap(c1, c2);
int ileWsumie = n / 2;
auto ilePoj = ilePojedynczych[c1] + ilePojedynczych[c2];
auto ilePod = ilePodwojnych[c1] + ilePodwojnych[c2];
auto cost1 = (ileWsumie - ilePod) * 2 - ilePoj;
if(n % 2 == 1) cost1 += iniCol[n - 1] != c1 && iniCol[n - 1] != c2;
if(n % 2 == 0) ileWsumie--;
ilePoj = ilePojedynczych2[c1] + ilePojedynczych2[c2];
ilePod = ilePodwojnych2[c1] + ilePodwojnych2[c2];
auto cost2 = (ileWsumie - ilePod) * 2 - ilePoj;
cost2 += iniCol[0] != c1 && iniCol[0] != c2;
if(n % 2 == 0) cost2 += iniCol[n - 1] != c1 && iniCol[n - 1] != c2;
auto cost = min(cost1, cost2);
ans[c1] = min(ans[c1], cost);
ans[c2] = min(ans[c2], cost);
}
void checkCols3(int c1, int c2) {
if(c1 > c2) swap(c1, c2);
int ileWsumie = n / 2;
auto ilePoj = ilePojedynczych[c1];
auto ilePod = ilePodwojnych[c1];
auto cost1 = (ileWsumie - ilePod) * 2 - ilePoj;
if(n % 2 == 1) cost1 += iniCol[n - 1] != c1 && iniCol[n - 1] != c2;
if(n % 2 == 0) ileWsumie--;
ilePoj = ilePojedynczych2[c1];
ilePod = ilePodwojnych2[c1];
auto cost2 = (ileWsumie - ilePod) * 2 - ilePoj;
cost2 += iniCol[0] != c1 && iniCol[0] != c2;
if(n % 2 == 0) cost2 += iniCol[n - 1] != c1 && iniCol[n - 1] != c2;
auto cost = min(cost1, cost2);
ans[c1] = min(ans[c1], cost);
ans[c2] = min(ans[c2], cost);
}
static inline pair<int, int> tQ(int l, int r) noexcept {
auto k = 63 - __builtin_clzll(r - l + 1);
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
rep(i, 0, n) cin >> iniCol[i];
//scanf("%d%d", &n, &m);
//rep(i, 0, n) scanf("%d", iniCol + i);
int xdd = 1;
tb = 1 << (64 - __builtin_clzll(max(xdd, m - 1)));
rep(i, 1, m + 1) ans[i] = 1e9;
rep(i, 0, n - 1) {
auto c1 = iniCol[i], c2 = iniCol[i + 1];
if(!ileTakich[pair{min(c1, c2), max(c1, c2)}] && !ileTakich2[pair{min(c1, c2), max(c1, c2)}]) skim[c1].pb(c2), skim[c2].pb(c1);
if(i % 2 == 0) {
if(c1 == c2) ilePodwojnych[c1]++;
else ilePojedynczych[c1]++, ilePojedynczych[c2]++, ileTakich[pair{min(c1, c2), max(c1, c2)}]++;
}
else {
if(c1 == c2) ilePodwojnych2[c1]++;
else ilePojedynczych2[c1]++, ilePojedynczych2[c2]++, ileTakich2[pair{min(c1, c2), max(c1, c2)}]++;
}
}
rep(i, 0, n - 1) if(iniCol[i] != iniCol[i + 1]) checkCols1(iniCol[i], iniCol[i + 1]);
rep(i, 1, m + 1) checkCols3(i, i);
rep(i, 1, m + 1) st[i - 1][0] = {ilePodwojnych[i] * 2 + ilePojedynczych[i], i - 1};
rep(k, 1, maxLog) rep(i, 0, m) st[i][k] = max(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
rep(i, 1, m + 1) {
pair<int, int> maxx = {-1, -1};
skim[i].pb(i);
ranges::sort(skim[i]);
auto prv = 1ll;
repIn(j, skim[i]) {
if(j > prv) maxx = max(maxx, tQ(prv - 1, j - 2));
prv = j + 1;
}
if(prv <= m) maxx = max(maxx, tQ(prv - 1, m - 1));
if(maxx.second >= 0) checkCols2(i, maxx.second + 1);
}
rep(i, 1, m + 1) st[i - 1][0] = {ilePodwojnych2[i] * 2 + ilePojedynczych2[i], i - 1};
rep(k, 1, maxLog) rep(i, 0, m) st[i][k] = max(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
rep(i, 1, m + 1) {
pair<int, int> maxx = {-1, -1};
auto prv = 1ll;
repIn(j, skim[i]) {
if(j > prv) maxx = max(maxx, tQ(prv - 1, j - 2));
prv = j + 1;
}
if(prv <= m) maxx = max(maxx, tQ(prv - 1, m - 1));
if(maxx.second >= 0) checkCols2(i, maxx.second + 1);
}
//rep(i, 0, m) printf("%d\n", ans[i + 1]);
rep(i, 0, m) cout << ans[i + 1] << '\n';
}
