#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MX=1000010, inf=2e9;
int n, m, A[MX];
int C[2][MX];
int ans[MX];
int idx[2][MX];
vector<int> G[2][MX];
void init(){
fill(ans+1, ans+m+1, inf);
for(int i=0; i<=n; i++){
C[i%2][A[i]]++; C[i%2][A[i+1]]++;
}
for(int i=1; i<n; i++){
if(A[i]==A[i+1]) continue;
G[i%2][A[i]].push_back(A[i+1]);
G[i%2][A[i+1]].push_back(A[i]);
}
iota(idx[0]+1, idx[0]+m+1, 1);
iota(idx[1]+1, idx[1]+m+1, 1);
sort(idx[0]+1, idx[0]+m+1, [](int a, int b){ return C[0][a]>C[0][b]; });
sort(idx[1]+1, idx[1]+m+1, [](int a, int b){ return C[1][a]>C[1][b]; });
}
void solve(){
int adj[MX]={};
for(int v=1; v<=m; v++){
for(int k=0; k<=1; k++){
int mx=0;
for(int x:G[k][v]) adj[x]++;
for(int x:G[k][v]){
mx=max(mx, C[k][x]-adj[x]);
}
for(int i=1; i<=m; i++){
int x=idx[k][i];
if(x!=v && adj[x]==0){
mx=max(mx, C[k][x]);
break;
}
}
for(int x:G[k][v]) adj[x]--;
ans[v]=min(ans[v], n-C[k][v]-mx);
}
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>A[i];
init();
solve();
for(int i=1; i<=m; i++) cout<<ans[i]<<'\n';
return 0;
}
