#include<bits/stdc++.h> using namespace std; void read(int &x){ x=0;char c=getchar(); for(;!isdigit(c);c=getchar()); for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48); } int n,m,a[200005]; vector<int>pos[200005]; bitset<200005>l,s; set<pair<int,int>>d; int sum,near; void deld(int p){ sum--; auto it=d.upper_bound({p,1e9}); if(it==d.begin())it=--d.upper_bound({p+n,1e9}); else it--; auto[l,r]=*it; near-=(r-l+1>>1); if(r-l+1==n){ near+=(n-1>>1); d.erase(it); if(n>1)if(p<n)d.insert({p+1,p+n-1});else d.insert({1,n-1}); return; } if(p<l)p+=n; near+=(p-l>>1),near+=(r-p>>1); d.erase(it); if(l<=p-1)d.insert({l,p-1}); if(p+1<=r)d.insert({p+1,r}); } void addd(int p){ sum++; d.insert({p,p}); auto it=d.lower_bound({p,p}); int l=p,r=p; if(it!=d.begin()){ auto it1=prev(it); if(it1->second==p-1){ l=it1->first; near-=(it1->second-it1->first+1>>1); d.erase(it1); } } else{ auto it1=prev(d.end()); if(it1->second==p+n-1){ l=it1->first; near-=(it1->second-it1->first+1>>1); d.erase(it1); // p+=n; } } if(p!=n){ auto it1=next(it); if(it1!=d.end()&&it1->first==p+1){ r=it1->second; near-=(it1->second-it1->first+1>>1); d.erase(it1); } } else{ auto it1=d.begin(); if(it1->first==1){ r=it1->second+n; near-=(it1->second-it1->first+1>>1); d.erase(it1); } } d.erase(it); if(r<l)r+=n; d.insert({l,r}); near+=(r-l+1>>1); } void dell(int p){ l[p]=0; if(s[(p-2+n)%n+1])deld((p-2+n)%n+1); if(s[p%n+1])deld(p); } void adds(int p){ s[p]=1; if(l[(p-2+n)%n+1])addd((p-2+n)%n+1); if(l[p%n+1])addd(p); } void slv(){ read(n),read(m); for(int i=1;i<=n;i++){ read(a[i]),pos[a[i]].push_back(i); } l.set(); for(int i=1;i<=m;i++){ if(pos[i].empty()){ cout<<"-1 "; continue; } for(int x:pos[i]){ dell(x); } cout<<n-pos[i].size()+sum-near<<" "; for(int x:pos[i]){ adds(x); } } } int main(){ slv(); return 0; }