Description：

给一个序列a，求一个不下降序列 $b$ ，使得各项依次做差求绝对值之和最小。

$1\leqslant n\leqslant 10^6$

Solution：

首先如果有一段他们的 $b$ 值都相同，那么显然这个 $b$ 应该是中位数，那么我们从前往后扫，首先令最后一个数这个区间的 $b$ 为这个数，然后如果它大于它上一个区间的 $b$ ，就把两个区间合并再取中位数，直到满足条件或者整个变成了一个区间，因此可以用左偏树维护 $\lceil\frac s 2\rceil$ 的值。然后这里要求严格上升，就把 $t[i]$ 变成 $t[i]-i$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int a[MAXN];

struct node

{

	int lc,rc;

	int d,val;

	int siz;

	node(){siz = 0;}

}t[MAXN];

int root[MAXN];

int merge(int a,int b)

{

	if(a == 0 || b == 0)return a + b;

	if(t[a].val < t[b].val)swap(a,b);

	t[a].rc = merge(t[a].rc,b);

	if(t[t[a].lc].d < t[t[a].rc].d)swap(t[a].lc,t[a].rc);

	t[a].d = t[t[a].rc].d + 1;

	t[a].siz = t[t[a].lc].siz + t[t[a].rc].siz + 1;

	return a;

}

struct seg

{

	int l,r,v,rt;

};

seg stack[MAXN];

int top = 0;

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)

	{

		root[i] = i;

		t[i].val = a[i] - i;

		t[i].siz = 1;

	}

	for(int i = 1;i <= n;++i)

	{

		int v = t[i].val,l = i,r = i;

		while(top != 0 && stack[top].v >= v)

		{

			root[i] = merge(root[i],stack[top].rt);

			l = stack[top].l;

			while(t[root[i]].siz > (r - l + 1 + 1) / 2)

			{

				root[i] = merge(t[root[i]].lc,t[root[i]].rc);

			}

			--top;

			v = t[root[i]].val;

		}

		stack[++top] = (seg){l,r,v,root[i]};

	}

	long long ans = 0;

	for(int i = 1;i <= top;++i)

	{

		for(int p = stack[i].l;p <= stack[i].r;++p)ans += abs(stack[i].v + p - a[p]);

	}

	cout << ans << endl;

	return 0;

}