#include <bits/stdc++.h>
template<typename T1, typename T2>
struct std::hash<std::pair<T1, T2>> {
static constexpr size_t p = 1'000'000'009;
size_t operator()(const std::pair<T1, T2> &obj) const {
return obj.first * p + obj.second;
}
};
int n;
size_t m;
std::vector<size_t> a;
std::vector<int> all_ans;
std::unordered_map<std::pair<size_t, size_t>, int> cnt2;
std::vector<int> cnt;
void update(int shift) {
std::vector<std::set<std::pair<int, size_t>>> d2(m);
std::set<std::pair<int, size_t>> d;
for (size_t i = 0; i < m; ++i) {
d.emplace(cnt[i] + cnt2[{i, i}], i);
}
for (int i = shift; i + 1 < n; i += 2) {
if (a[i] != a[i + 1]) {
d2[a[i]].emplace(cnt[a[i + 1]] + cnt2[{a[i + 1], a[i + 1]}] - cnt2[{a[i], a[i + 1]}], a[i + 1]);
d2[a[i + 1]].emplace(cnt[a[i]] + cnt2[{a[i], a[i]}] - cnt2[{a[i], a[i + 1]}], a[i]);
}
}
int base_ans = n;
for (size_t f = 0; f < m; ++f) {
base_ans = std::min(base_ans, n - cnt2[{f, f}] - cnt[f]);
}
for (size_t f = 0; f < m; ++f) {
int ans = base_ans;
if (!d2[f].empty()) ans = std::min(ans, n - cnt[f] - cnt2[{f, f}] - (--d2[f].end())->first);
for (auto [x, y]: d2[f]) {
d.erase({cnt[y] + cnt2[{y, y}], y});
}
d.erase({cnt[f] + cnt2[{f, f}], f});
if (!d.empty()) ans = std::min(ans, n - cnt[f] - cnt2[{f, f}] - (--d.end())->first);
d.insert({cnt[f] + cnt2[{f, f}], f});
for (auto [x, y]: d2[f]) {
d.insert({cnt[y] + cnt2[{y, y}], y});
}
all_ans[f] = std::min(all_ans[f], ans);
}
}
int main() {
// freopen("main.in", "r", stdin);
// freopen("main.out", "w", stdout);
std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
std::cin >> n >> m;
a.resize(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
--a[i];
}
all_ans.resize(m, n);
cnt2.clear();
cnt.assign(m, {});
for (int i = 0; i < n; i += 2) {
if (i + 1 < n) {
cnt2[{a[i], a[i + 1]}]++, cnt[a[i]]++;
if (a[i] != a[i + 1]) cnt2[{a[i + 1], a[i]}]++, cnt[a[i + 1]]++;
} else {
cnt[a[i]]++;
}
}
update(0);
cnt2.clear();
cnt.assign(m, 0);
for (int i = -1; i < n; i += 2) {
if (i + 1 < n && i > 0) {
cnt2[{a[i], a[i + 1]}]++, cnt[a[i]]++;
if (a[i] != a[i + 1]) cnt2[{a[i + 1], a[i]}]++, cnt[a[i + 1]]++;
} else {
if (i + 1 == n) cnt[a[i]]++;
else cnt[a[i + 1]]++;
}
}
update(1);
for (size_t i = 0; i < m; ++i) {
std::cout << all_ans[i] << '\n';
}
}
