#include "bits/stdc++.h"
using namespace std;
#define ar array
const int N = 1e6 + 5;
int a[N], res[N], cc[N];
map<int, int> edges[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i];
a[i]--;
}
{
memset(cc, 0, sizeof cc);
for(int i=1;i+1<n;i+=2){
if(a[i] != a[i+1]){
edges[a[i]][a[i+1]]++;
edges[a[i+1]][a[i]]++;
}
}
multiset<int> ss;
for(int i=0;i<n;i++){
cc[a[i]]++;
}
for(int i=0;i<m;i++) ss.insert(cc[i]);
for(int i=0;i<m;i++){
int rr = 0;
ss.erase(ss.find(cc[i]));
for(auto x : edges[i]){
ss.erase(ss.find(cc[x.first]));
rr = max(rr, cc[x.first] - x.second);
//~ cout<<i<<" "<<x.first<<" "<<cc[x.first]<<" "<<x.second<<"\n";
}
if(!ss.empty()) rr = max(rr, *ss.rbegin());
res[i] = max(res[i], rr + cc[i]);
for(auto x : edges[i]){
ss.insert(cc[x.first]);
}
ss.insert(cc[i]);
edges[i].clear();
}
}
{
memset(cc, 0, sizeof cc);
for(int i=0;i+1<n;i+=2){
if(a[i] != a[i+1]){
edges[a[i]][a[i+1]]++;
edges[a[i+1]][a[i]]++;
}
}
multiset<int> ss;
for(int i=0;i<n;i++){
cc[a[i]]++;
}
for(int i=0;i<m;i++) ss.insert(cc[i]);
for(int i=0;i<m;i++){
int rr = 0;
ss.erase(ss.find(cc[i]));
for(auto x : edges[i]){
ss.erase(ss.find(cc[x.first]));
rr = max(rr, cc[x.first] - x.second);
//~ cout<<i<<" "<<x.first<<" "<<cc[x.first]<<" "<<x.second<<"\n";
}
if(!ss.empty()) rr = max(rr, *ss.rbegin());
res[i] = max(res[i], rr + cc[i]);
for(auto x : edges[i]){
ss.insert(cc[x.first]);
}
ss.insert(cc[i]);
edges[i].clear();
}
}
for(int i=0;i<m;i++) cout<<n - res[i]<<"\n";
}
