#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
ll n,q,s,t,a,b,c,d,k,m;
vector<ll>v2;
ll cnt[1000007];
ll ans[1000007];
vector<pair<ll,ll>>licz;
vector<pair<ll,ll>>v;//kolor,ile
map<pair<ll,ll>,vector<pair<pair<ll,ll>,pair<ll,bool>>>>mp;//para mniejszy wiekszy -> pocz,kon(pocz2-1),kon2,czymniejszyprzed
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
m++;
cin>>a;
v2.pb(a);
cnt[a]++;
for(ll i=1;i<n;i++){
cin>>a;
cnt[a]++;
if(a==v2.back()){
c++;
v2.pb(a);}
else{
v.pb({v2.back(),c});
c=1;
v2.pb(a);
}
}
v.pb({v2.back(),c});
ll sm=0;
for(ll i=1;i<v.size();i++){
auto pom1=v[i-1],pom2=v[i];
mp[{min(pom1.ff,pom2.ff),max(pom1.ff,pom2.ff)}].pb({{sm,sm+pom1.ss},{sm+pom1.ss+pom2.ss,pom1.ff<pom2.ff}});
sm+=pom1.ss;
}
for(ll i=1;i<=m;i++){
licz.pb({cnt[i],i});
ans[i]=INFL;
}
sort(licz.begin(),licz.end());
reverse(licz.begin(),licz.end());
for(ll i=1;i<=m;i++){
for(ll j=0;j<=m;j++){
if(licz[j].ss==i)continue;
if(mp[{min(i,licz[j].ss),max(i,licz[j].ss)}].empty()){
ans[i]=min(ans[i],n-cnt[i]-licz[j].ff);
// cout<<i<<": "<<ans[i]<<"\n";
break;
}
else{
auto pom=mp[{min(i,licz[j].ss),max(i,licz[j].ss)}];
sort(pom.begin(),pom.end());
ll iledod=0;
ll koszt[2];
koszt[pom[0].ff.ss%2]=0;
koszt[(pom[0].ff.ss+1)%2]=1;
for(ll k=1;k<pom.size();k++){
// cout<<i<<": "<<koszt[0]<<" "<<koszt[1]<<"\n";
ll pom1=min(koszt[pom[k].ff.ss%2],koszt[(pom[k].ff.ss+1)%2]+1);
koszt[(pom[k].ff.ss+1)%2]=min(koszt[(pom[k].ff.ss+1)%2]+1,koszt[(pom[k].ff.ss)%2]+2);
koszt[pom[k].ff.ss%2]=pom1;
}
ans[i]=min(ans[i],n-cnt[i]-licz[j].ff+min(koszt[0],koszt[1]));
}
}
}
for(ll i=1;i<m;i++)cout<<ans[i]<<"\n";
}
