#include "bits/extc++.h"
using namespace std;
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t;
((cerr << " | " << u), ...);
cerr << endl;
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
inline void init_io() {
cin.tie(nullptr);
cin.exceptions(ios::failbit);
ios_base::sync_with_stdio(false);
}
template <typename T>
vector<T>& operator+=(vector<T>& a, const vector<T>& b) {
a.insert(end(a), begin(b), end(b));
return a;
}
template <typename T>
vector<T> operator+(vector<T> a, const vector<T>& b) {
return a += b;
}
struct DS {
vector<int> arr;
multiset<int> ms;
DS(int n) : arr(n) {
for (int i = 0; i < n; i++) {
ms.insert(0);
}
}
void update_add(int ind, int x) {
ms.erase(ms.find(arr[ind]));
ms.insert(arr[ind] += x);
}
void update_set(int ind, int x) {
ms.erase(ms.find(arr[ind]));
ms.insert(arr[ind] = x);
}
int query_max() const {
return *rbegin(ms);
}
int operator[](int ind) const {
return arr[ind];
}
};
vector<int> solve(int m, const vector<int>& arr) {
int n = sz(arr);
assert(n % 2 == 0);
DS cnto(m);
vector<int> cnt2(m);
vector<vector<int>> graph(m);
for (int i = 0; i < n; i += 2) {
int a = arr[i], b = arr[i + 1];
cnto.update_add(a, +1);
cnto.update_add(b, +1);
if (a == b) {
cnt2[a]++;
continue;
}
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int> ans(m);
for (int c = 0; c < m; c++) {
int cx = 0;
for (auto& v : graph[c]) {
cnto.update_add(v, -1);
}
int tmpr = cnto[c];
cnto.update_set(c, 0);
cx += 2 * cnt2[c];
cx += sz(graph[c]);
cx += cnto.query_max();
ans[c] = n - cx;
for (auto& v : graph[c]) {
cnto.update_add(v, +1);
}
cnto.update_set(c, tmpr);
}
return ans;
}
void solve() {
int n, m;
cin >> n >> m;
vector<int> arr(n);
for (auto& a : arr) {
cin >> a;
a--;
}
vector<int> ans(m, 1e9);
auto go = [&](const vector<int>& narr, int dd) -> void {
auto cans = solve(m + dd, narr);
for (int i = 0; i < m; i++) {
ans[i] = min(ans[i], cans[i] - dd);
}
};
if (n % 2 == 0) {
go(arr, 0);
go(vector {m} + arr + vector {m + 1}, 2);
} else {
go(arr + vector {m}, 1);
go(vector {m} + arr, 1);
}
for (auto& a : ans) {
cout << a << endl;
}
}
int main() {
init_io();
solve();
}
