#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
ll readint(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,c[1000005],cnt[1000005],res[1000005];
vector<int> g[1000005];
void solve(int x){
for(int i=1;i<=m;i++){
cnt[i]=0;
g[i].clear();
}
for(int i=1;i<=n;i++) cnt[c[i]]++;
for(int i=1+x;i+1<=n;i+=2){
if(c[i]==c[i+1]) continue;
g[c[i]].push_back(c[i+1]);
g[c[i+1]].push_back(c[i]);
}
multiset<int> st;
for(int i=1;i<=m;i++) st.insert(cnt[i]);
for(int i=1;i<=m;i++){
vector<int> xs;
for(int j:g[i]) xs.pb(j);
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
for(int j:xs) st.erase(st.find(cnt[j]));
for(int j:g[i]) cnt[j]--;
for(int j:xs) st.insert(cnt[j]);
st.erase(st.find(cnt[i]));
int mx=0;
if(!st.empty()) mx=*prev(st.end());
res[i]=min(res[i],n-(cnt[i]+mx));
st.insert(cnt[i]);
for(int j:xs) st.erase(st.find(cnt[j]));
for(int j:g[i]) cnt[j]++;
for(int j:xs) st.insert(cnt[j]);
}
}
int main() {
n=readint(); m=readint();
for(int i=1;i<=n;i++) c[i]=readint();
for(int i=1;i<=m;i++) res[i]=n;
solve(0);
solve(1);
for(int i=1;i<=m;i++) printf("%d\n",res[i]);
return 0;
}
