#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 1000006;
int nn;
int n, m;
int c[N];
pair<int, int> a[N];
int ans[N];
vector<int> v[N];
int q[N];
int qq[N];
int maxu;
void ubd(int i, int y)
{
if (a[i].fi)
qq[q[a[i].fi]]--;
if (a[i].se && a[i].se != a[i].fi)
qq[q[a[i].se]]--;
q[a[i].fi] += y;
q[a[i].se] += y;
if (a[i].fi)
qq[q[a[i].fi]]++;
if (a[i].se && a[i].se != a[i].fi)
qq[q[a[i].se]]++;
while (1)
{
if (qq[maxu + 1])
++maxu;
else if (qq[maxu + 2])
maxu += 2;
else
break;
}
while (!qq[maxu])
--maxu;
}
void solvv()
{
for (int x = 1; x <= m; ++x)
v[x].clear();
memset(q, 0, sizeof q);
memset(qq, 0, sizeof qq);
maxu = 0;
for (int i = 1; i <= n; ++i)
{
v[a[i].fi].push_back(i);
if (a[i].se != a[i].fi)
v[a[i].se].push_back(i);
}
qq[0] = m;
for (int i = 1; i <= n; ++i)
ubd(i, 1);
for (int x = 1; x <= m; ++x)
{
int yans = 0;
for (int i = 0; i < sz(v[x]); ++i)
{
int j = v[x][i];
ubd(j, -1);
if (a[j].fi == x)
++yans;
if (a[j].se == x)
++yans;
}
yans += maxu;
ans[x] = min(ans[x], nn - yans);
for (int i = 0; i < sz(v[x]); ++i)
{
int j = v[x][i];
ubd(j, 1);
}
}
}
void solv()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> c[i];
nn = n;
for (int i = 1; i <= m; ++i)
ans[i] = n;
if (n % 2 == 0)
{
for (int i = 1; i <= n; i += 2)
{
a[i / 2 + 1] = m_p(c[i], c[i + 1]);
}
n = n / 2;
solvv();
n *= 2;
a[1] = m_p(c[1], 0);
a[2] = m_p(c[n], 0);
for (int i = 2; i < n; i += 2)
{
a[i / 2 + 2] = m_p(c[i], c[i + 1]);
}
n = 2 + (n - 2) / 2;
solvv();
}
else
{
a[1] = m_p(c[1], 0);
for (int i = 2; i <= n; i += 2)
a[i / 2 + 1] = m_p(c[i], c[i + 1]);
n = (n - 1) / 2 + 1;
solvv();
n = (n - 1) * 2 + 1;
a[1] = m_p(c[n], 0);
for (int i = 1; i < n; i += 2)
a[i / 2 + 2] = m_p(c[i], c[i + 1]);
solvv();
}
for (int i = 1; i <= m; ++i)
cout << ans[i] << "\n";
}
int main()
{
#ifdef SOMETHING
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // SOMETHING
ios_base::sync_with_stdio(false), cin.tie(0);
int tt = 1;
//cin >> tt;
while (tt--)
{
solv();
}
return 0;
}
