#include <bits/stdc++.h>
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 4e18;
const int OO = 0;
const int OOO = 1;
using namespace std;
const int N = 1e6 + 10;
int n, m, a[N];
vector<int> pos[N];
int mx;
int freq[N] = {};
int freq_count[N] = {};
void add(int val) {
if (OO) cout << "adding " << val << '\n';
--freq_count[freq[val]];
++freq[val];
++freq_count[freq[val]];
mx = max(mx, freq[val]);
}
void del(int val) {
if (OO) cout << "deleting " << val << '\n';
--freq_count[freq[val]];
if (mx == freq[val] && !freq_count[freq[val]])
--mx;
--freq[val];
++freq_count[freq[val]];
}
int query() {
if (OO) cout << "query: " << mx << '\n';
return mx;
}
void prep() {
freq_count[0] = n;
mx = 0;
for (int i = 0; i < n; i++)
add(a[i]);
}
int solve(int v) {
if (OO) cout << "started solve(" << v << "):\n";
vector<int> even, odd;
for (const auto &i : pos[v]) {
int e = (i & 1) ? i - 1 : i;
int o = (i & 1) ? i : i - 1;
if (!even.size() || even.back() != e) even.push_back(e);
if (o > 0 && (!odd.size() || odd.back() != o)) odd.push_back(o);
}
int start, remain, mn = md;
// try even
start = 0;
remain = n;
for (const auto &i : even) {
del(a[i]);
remain--;
if (a[i] != v)
start++;
if (i + 1 < n) {
del(a[i + 1]);
remain--;
if (a[i + 1] != v)
start++;
}
}
mn = min(mn, start + remain - query());
for (const auto &i : even) {
add(a[i]);
if (i + 1 < n)
add(a[i + 1]);
}
// try odd
start = 0;
remain = n;
if (a[0] == v) {
del(a[0]);
remain--;
}
for (const auto &i : odd) {
del(a[i]);
remain--;
if (a[i] != v)
start++;
if (i + 1 < n) {
del(a[i + 1]);
remain--;
if (a[i + 1] != v)
start++;
}
}
mn = min(mn, start + remain - query());
if (a[0] == v)
add(a[0]);
for (const auto &i : odd) {
add(a[i]);
if (i + 1 < n)
add(a[i + 1]);
}
return mn;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
--a[i];
pos[a[i]].push_back(i);
}
prep();
for (int i = 0; i < m; i++)
cout << solve(i) << '\n';
}
