#include<bits/stdc++.h> using namespace std; #define int long long #define pb push_back const int MAXN=500010; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} int n,m,a[MAXN],p[MAXN],s[MAXN],h[MAXN]; struct segtree{ #define lson (pos<<1) #define rson (pos<<1|1) struct nd{ int L,R,sum,len; }t[MAXN<<2]; void pushup(int pos){ t[pos].L=t[lson].L==t[lson].len?t[lson].L+t[rson].L:t[lson].L; t[pos].R=t[rson].R==t[rson].len?t[rson].R+t[lson].R:t[rson].R; t[pos].sum=t[lson].sum+t[rson].sum; if(t[lson].L!=t[lson].len&&t[rson].R!=t[rson].len)t[pos].sum+=t[lson].R+t[rson].L-(t[lson].R+t[rson].L)/2; } void build(int pos,int l,int r){ t[pos].len=r-l+1; if(l==r){ t[pos].L=t[pos].R=h[l]&&h[l-1]&&h[l]!=h[l-1]; return; } int mid=(l+r)>>1; build(lson,l,mid),build(rson,mid+1,r); pushup(pos); } void update(int pos,int l,int r,int x){ if(l==r){ t[pos].L=t[pos].R=h[l]&&h[l-1]&&h[l]!=h[l-1]; return; } int mid=(l+r)>>1; if(x<=mid)update(lson,l,mid,x); if(x>mid)update(rson,mid+1,r,x); pushup(pos); } void prt(int pos,int l,int r){ if(l==r){ cout<<t[pos].L<<" "; return; } int mid=(l+r)>>1; prt(lson,l,mid),prt(rson,mid+1,r); } }T; vector<int>G[MAXN]; void upd(int x){ if(!x||x>n)return; T.update(1,1,n,x); } void slv(){ n=read(),m=read(); for(int i=1;i<=n;i++)G[a[i]=read()].pb(i); G[a[n]].pb(0); for(int i=0;i<=n;i++)h[i]=1; T.build(1,1,n); for(int i=1;i<=m;i++)if(!G[i].empty()){ for(auto o:G[i])h[o]=0,upd(o),upd(o+1); printf("%lld ",n-G[i].size()+(a[n]==i)+T.t[1].sum+T.t[1].L+T.t[1].R-(T.t[1].L+T.t[1].R)/2); for(auto o:G[i])h[o]=-1,upd(o),upd(o+1); }else printf("-1 "); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); return 0; }