§ Description

Link.

Given is a sequencen $A$ of $n$ intergers.

Construct a stricly increasing sequence $B$ of $n$ intergers that makes the sum of $|B_{i}-A_{i}|$ the smallest.

§ Solution

First, we make $a_{i}:=a_{i}-i$. Then we just make "strictly increasing" become "unstrictly increasing".

1. for $a_{1}\le a_{2}\le\cdots\le a_{n}$:

   When $B$ is the same as $A$, it gets the minimum answer.

2. for $a_{1}\ge a_{2}\ge\cdots\ge a_{n}$:

   When for each $i$, $B_{i}=A_{\lfloor\frac{n}{2}\rfloor}$, it gets the minimum answer.

Maybe we can divide $A$ into m parts.

Such like: $[l_{1},r_{1}],\cdots,[l_{m},r_{m}]$

that satisfies: for each $i$, sequence $A[l_{i},r_{i}]$ is unstrictly increasing/decreasing.

So we can get the answer to each interval.

Let's consider how to merge the answers.

When we're merging two intervals, we can just get the new median of the two intervals.

---

So things above are just bullshit.

Parallel Searching!

FUCK YOU.

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1e18;
int n;
LL a[1000010],b[1000010],ans;
void solve(LL l,LL r,int fr,int ba)
{
	if(l>=r||fr>ba)	return;
	LL mid=(l+r)>>1,tmp=0,mn=INF,pos=0;
	for(int i=fr;i<=ba;++i)	tmp+=abs(a[i]-mid-1);
	mn=tmp,pos=fr-1;
	for(int i=fr;i<=ba;++i)
	{
		tmp-=abs(a[i]-mid-1);
		tmp+=abs(a[i]-mid);
		if(tmp<mn)	mn=tmp,pos=i;
	}
	for(int i=fr;i<=pos;++i)	b[i]=mid;
	for(int i=pos+1;i<=ba;++i)	b[i]=mid+1;
	solve(l,mid,fr,pos),solve(mid+1,r,pos+1,ba);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)	scanf("%lld",&a[i]),a[i]-=i;
	solve(-INF,INF,1,n);
	for(int i=1;i<=n;++i)	ans+=abs(a[i]-b[i]);
	printf("%lld\n",ans);
	for(int i=1;i<=n;++i)	printf("%lld ",b[i]+i);
	return 0;
}