从P4597过来的，看到有大佬写整体二分，细想了思路很巧妙（先膜拜一下），又根据b数组的取值一定在a数组中，自己写了一版离散化的整体二分，在那道题是过了的。

然鹅，搬到这道题发现喜提60分。大胆猜测是不是严格单调增后不满足b数组的值一定在a数组中出现，所以写挂了，于是写了一版不离散的整体二分，就过了。但是看了下题解，发现堆写法里面的元素都是a数组的值，所以问题不是出在这里，以为是long long的问题，结果全开了也没过，所以希望哪位大佬能看看蒟蒻的代码哪里有问题，十分感谢！

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
typedef long long ll;
int n,a[N],a1[N],b[N];
ll ans;

void solve(int lv,int rv,int l,int r)
{
	if(l>r) return;
	if(lv==rv)
	{
		for(int i=l;i<=r;i++) b[i]=a1[lv];
		return;
	}
	int mid=(lv+rv)>>1;
	ll tot=0;
	for(int i=l;i<=r;i++) tot+=abs((ll)a[i]-a1[mid+1]);
	ll minn=tot;
	int k=l-1;
	for(int i=l;i<=r;i++)
	{
		tot-=abs((ll)a[i]-a1[mid+1]);tot+=abs((ll)a[i]-a1[mid]);
		if(tot<minn)
		{
			minn=tot;
			k=i;
		}
	}
	solve(lv,mid,l,k);solve(mid+1,rv,k+1,r);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i]-=i;
		a1[i]=a[i];
	}
	sort(a1+1,a1+n+1);
	solve(1,n,1,n);
	for(int i=1;i<=n;i++) ans+=abs((ll)a[i]-b[i]);
	printf("%lld\n",ans);
	for(int i=1;i<=n;i++) printf("%d ",b[i]+i);
	printf("\n");
	return 0;
}