///
/// ♪ Hashire sori yo ♪
/// ♪ Kaze no you ni ♪
/// ♪ Tsukimihara wo ♪
/// ♪ PADORU PADORU ♪
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 1<<20;
int a[N];
vector<pii> vec[N];
int n, m;
int cnt[N];
priority_queue<pii> pq;
vector<pii> record;
bool recording;
void add(int c, int x)
{
if (recording)
record.push_back({c, cnt[c]});
cnt[c] += x;
pq.push({cnt[c], c});
}
void revert()
{
recording = 0;
while (record.size()) {
auto [c, x] = record.back();
record.pop_back();
add(c, x-cnt[c]);
}
}
int get_max()
{
while (pq.top().first != cnt[pq.top().second])
pq.pop();
return pq.top().first;
}
int count(int c, bool odd)
{
recording = 1;
int cntc = cnt[c];
int ans = 0;
add(c, -cntc);
vector<pair<pii,bool>> v;
int lst = 0;
for (auto [l, r] : vec[c]) {
if (lst != l)
v.push_back({{lst, l}, 0});
v.push_back({{l, r}, 1});
lst = r;
}
if (lst != n)
v.push_back({{lst, n}, 0});
for (auto [lr, is] : v) {
auto [l, r] = lr;
if (r == n)
break;
odd ^= (r - l) & 1;
if (odd) {
++cntc;
++ans;
add(a[r - 1 + is], -1);
}
}
ans += n - cntc - get_max();
revert();
return ans;
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
Loop (i,0,n) {
cin >> a[i];
--a[i];
}
int lst = 0;
Loop (i,0,n) {
if (a[i] != a[lst]) {
vec[a[lst]].push_back({lst, i});
lst = i;
}
add(a[i], 1);
}
vec[a[lst]].push_back({lst, n});
Loop (i,0,m) {
int ans = min(count(i, 0), count(i, 1));
cout << ans << '\n';
}
}
