通过手玩，易知只有大于或小于当前数 (k) 的状态才会对答案有所影响，也就是说当前数的大小不重要，重要的是与 (k) 的大小关系。
这样原来的序列只有两种：
-
({k,>k,>k,>k,>k,dots}) 或 ({k,<k,<k,<k,<k,dots})
-
({k,>k,<k,>k,<k,dots})
对于第一种，显然，对答案贡献为 (sum_{i=1}^{len} [a_i eq k]) 。
对于第二种，我们每次必须把下一个元素先 copy 成更小或更大后才能转换成 (k) ，而被 copy 的元素将能被直接转换 (k) 。
显然有贡献 ((sum_{i=1}^{len} [a_i eq k])+lfloor frac{len}{2} floor) 。
这样分类后，显然只要原序列中有数字 (k) ，对于 (k) 就有解。
所以现在的问题转化成如何求出 (lfloor frac{len}{2} floor) ，进一步转化成维护一个如第二类的序列，也是线段树的一个经典题目，具体相似于最大子序列问题。
首先当然是断环成链。
考虑每次转换 (k) 值时，只有值为 (k-1) 和 (k) 的元素性质会发生变化，每次只要修改这些节点即可，存储可用 std::vector 或手写链表实现，查询时选取一段合适的长度为 (n+1) 的区间即可
时间复杂度 (mathcal{O}(nlog n))
Code(C++98):
#include<bits/stdc++.h>
#define forn(i,s,t) for(int i=(s);i<=(t);++i)
using namespace std;
const int N = 2e5+3;
char ch;
template<typename T>inline void redn(T &ret) { // 快读
ret=0,ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) ret=(ret<<1)+(ret<<3)+ch-48,ch=getchar();
}
vector<int> v[N];
int n,m,a[N<<1],now;
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
struct Node{int l,r,dl,dr,len,lng;}T[N<<4]; //线段树 变量(从左到右)：区间左/右端 以左/右端为端点的最长序列长度
// 区间长度 该区间序列长度贡献总和
inline Node Mrg(Node L,Node R) { // 合并区间
Node M = (Node){0,0,0,0,0,0};
bool flag = 1ll*(a[L.r]-now)*(a[R.l]-now)<0?1:0;
M.dl = L.dl+(L.len==L.dl&&flag)*R.dl;
M.dr = R.dr+(R.len==R.dr&&flag)*L.dr;
M.l = L.l,M.r = R.r,M.len = L.len+R.len;
if(flag) M.lng = L.lng+R.lng-(L.dr>>1)-(R.dl>>1)+(L.dr+R.dl>>1);
else M.lng = L.lng+R.lng;
return M;
}
void Bld(int p,int l,int r) { // 建树
if(l == r) {
if(now == a[l]) T[p] = (Node){l,r,0,0,r-l+1,0};
else T[p] = (Node){l,r,1,1,r-l+1,0};
return ;
}
int mid = l+r >> 1;
Bld(ls(p),l,mid),Bld(rs(p),mid+1,r);
T[p] = Mrg(T[ls(p)],T[rs(p)]);
}
void Upd(int p,int nl,int nr,int pos) { // 更新
if(nl == nr) {
if(now == a[nl]) T[p] = (Node){nl,nr,0,0,nr-nl+1,0};
else T[p] = (Node){nl,nr,1,1,nr-nl+1,0};
return ;
}
int mid = nl+nr >> 1;
if(pos<=mid) Upd(ls(p),nl,mid,pos);
else Upd(rs(p),mid+1,nr,pos);
T[p] = Mrg(T[ls(p)],T[rs(p)]);
}
Node Qry(int p,int l,int r,int nl,int nr) { //查询
if(l==nl&&nr==r) return T[p];
int mid = nl+nr >> 1;
if(r<=mid) return Qry(ls(p),l,r,nl,mid);
else if(l>mid) return Qry(rs(p),l,r,mid+1,nr);
else return Mrg(Qry(ls(p),l,mid,nl,mid),Qry(rs(p),mid+1,r,mid+1,nr));
}
int main() {
redn(n),redn(m);
forn(i,1,n) redn(a[i]),a[i+n]=a[i];
forn(i,1,n) v[a[i]].push_back(i);
Bld(1,1,n<<1);
forn(i,1,m) { now = i; int count = 0;
if(v[i].size())
forn(j,0,v[i].size()-1) Upd(1,1,n<<1,v[i][j]),Upd(1,1,n<<1,v[i][j]+n);
if(v[i-1].size())
forn(j,0,v[i-1].size()-1) Upd(1,1,n<<1,v[i-1][j]),Upd(1,1,n<<1,v[i-1][j]+n);
if(!v[i].size()) printf("-1 ");
else printf("%d ",n-(int)v[i].size()+Qry(1,v[i][0],v[i][0]+n,1,n<<1).lng);
}
return 0;
}