#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

struct segtree{
    static const int SEG=1<<20;
    vint dat;
    segtree():dat(SEG*2){}
    void update(int k,int x){
        k+=SEG-1;
        dat[k]=x;
        while(k){
            k=(k-1)/2;
            dat[k]=max(dat[k*2+1],dat[k*2+2]);
        }
    }
    int get(int a,int b,int k=0,int l=0,int r=SEG){
        if(r<=a||b<=l)return 0;
        if(a<=l&&r<=b)return dat[k];
        return max(get(a,b,k*2+1,l,(l+r)/2),get(a,b,k*2+2,(l+r)/2,r));
    }
};

int N,M;
int C[1111111];

int cnt[1111111];
int base[1111111];
vint G[1111111];

int ans[1111111];

signed main(){
    scanf("%lld%lld",&N,&M);
    rep(i,N)scanf("%lld",&C[i]),C[i]--;

    rep(i,N)cnt[C[i]]++;

    fill_n(ans,M,N);

    rep(lattemalta,2){
        rep(i,M)G[i].clear();
        memset(base,0,sizeof(base));
        segtree seg;
        rep(i,M)seg.update(i,cnt[i]);
        vint b;
        if(lattemalta==1)b.pb(C[0]);

        int cur=lattemalta;
        while(cur+1<N){
            if(C[cur]==C[cur+1]){
                base[C[cur]]+=2;
            }
            else{
                G[C[cur]].pb(C[cur+1]);
                G[C[cur+1]].pb(C[cur]);
            }
            cur+=2;
        }
        if(cur>N)b.pb(C[N-1]);

        rep(i,M){
            int a=N-cnt[i];
            int cost=G[i].size();

            for(auto t:G[i]){
                cnt[t]--;
                a--;
                seg.update(t,cnt[t]);
            }

            int tmp=0;
            if(i)tmp=seg.get(0,i);
            if(i+1!=M)chmax(tmp,seg.get(i+1,M));
            chmin(ans[i],cost+a-tmp);

            for(auto t:G[i]){
                cnt[t]++;
                seg.update(t,cnt[t]);
            }
        }
    }

    rep(i,M)printf("%lld\n",ans[i]);
    return 0;
}