考慮兩種情況：
1.(a_1)<(a_2)<(a_3)<(a_4)...<(a_n)
直接令(b_i)=(a_i),最小。
2.(a_1)>(a_2)>(a_3)>(a_4)...>(a_n)
初一的一道絕對值題是這題的弱化版。
給定(a_1),(a_2)...(a_n),求一點x，使得(abs(a_1-x))+(abs(a_2-x))...+(abs(a_n-x))值最小
直接求中位數即可（初一的知識——絕對值）
同理，關于2.我們令(b_i)取1到i中位數即可。
那麼這道題我們就可以看做是許多個嚴格遞減的序列，每一個序列的答案我們是可以知道的。是以我們所要做的就是合并答案即可。
怎麼維護每一次合并呢？
我們想到了左偏樹。
對于左偏樹，我們每放入一個新節點，我們就(-=i),使得原應嚴格下降的序列變成(a_{i-1}>=a_i),再判斷新加入的節點是否符合這個規則，不符合就與上一個merge。
因為我們是要求中位數，是以節點的size不應超過它的範圍的二分之一再(+1)，是以我們要一直(size--)，同時删除這個節點。
最後我們求答案即可。
注：因為我們一開始就減去了i，是以在如果要輸出序列是要加上i。
#include<bits/stdc++.h>
using namespace std;
struct data
{
int l,r,size,fa,val;
}s[1000001];
int val[1000001],n,k,cnt,ch[1000001][2],dis[1000001];
long long ans;
int merge(int x,int y)
{
if(!x||!y)
{
return x+y;
}
if(val[x]<val[y])
{
swap(x,y);
}
ch[x][1]=merge(ch[x][1],y);
if(dis[ch[x][0]]<dis[ch[x][1]])
{
swap(ch[x][0],ch[x][1]);
}
dis[x]=dis[ch[x][1]]+1;
return x;
}
int read()
{
char ch=getchar();
int sum=0,f=1;
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
sum=sum*10+ch-'0';
ch=getchar();
}
return sum*f;
}
int main()
{
n=read();
dis[0]=-1;
for(int i=1;i<=n;i++)
{
val[i]=read();
val[i]-=i;
}
for(int i=1;i<=n;i++)
{
s[++cnt]=(data){
i,i,1,i,val[i]
};
while(cnt!=1&&s[cnt-1].val>s[cnt].val)
{
cnt--;
s[cnt].fa=merge(s[cnt].fa,s[cnt+1].fa);
s[cnt].size+=s[cnt+1].size;
s[cnt].r=s[cnt+1].r;
while(s[cnt].size>(s[cnt].r-s[cnt].l+3)/2)
{
s[cnt].size--;
s[cnt].fa=merge(ch[s[cnt].fa][0],ch[s[cnt].fa][1]);
}
s[cnt].val=val[s[cnt].fa];
}
}
int m=1;
for(int i=1;i<=n;i++)
{
if(i>s[m].r)
{
m++;
}
ans+=abs(s[m].val-val[i]);
}
printf("%lld
",ans);
m=1;
for(int i=1;i<=n;i++)
{
if(i>s[m].r)
{
m++;
}
printf("%d ",s[m].val+i);
}
return 0;
}