Description

Input

Output

一个整数R

Sample Input

7

9

4

8

20

14

15

18

Sample Output

13

HINT

所求的Z序列为6,7,8,13,14,15,18.

R=13

/*  思维很扭曲（反正我想不出来）的一道题。  先想想不下降的：   考虑一个正序的序列，z[i]=t[i]   考虑一个逆序的序列，z[i]=x(x是逆列的中位数）  既然是这样那么我们就可以把整个序列化分成逆序的若干段，对于每段求中位数（正序的可看成num个逆序的）。  维护中位数用左偏树，具体方法是始终保持堆中数的个数不大于原数个数的一半。  至于改成上升的，把原序列t[i]-=i。    PS：题解中的root[i]和堆中下标的关系把我看蒙了，所以这里说一下。      代码中是建立了n个堆，然而不断合并，最终变成了tot个。      root[i]表示第i个堆(合并后的)的堆顶是哪个元素。 */#include
      
       #include
       
        #include
        
         #define N 1000010using namespace std;int t[N],root[N],l[N],r[N],num[N],cnt[N],n,tot;struct node{    int l,r,dis,w;};node heap[N];int merge(int a,int b){    if(a==0||b==0)return a+b;    if(heap[a].w
         
          heap[heap[a].l].dis)        swap(heap[a].r,heap[a].l);    heap[a].dis=heap[heap[a].r].dis+1;    return a;}int pop(int a){    return merge(heap[a].l,heap[a].r);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d",&t[i]),t[i]-=i;    for(int i=1;i<=n;i++){        ++tot;        l[tot]=r[tot]=i;        num[tot]=cnt[tot]=1;        root[tot]=i;        heap[i].dis=heap[i].l=heap[i].r=0;        heap[i].w=t[i];                while(tot>1&&heap[root[tot]].w
          
           num[tot]+1;--cnt[tot])                root[tot]=pop(root[tot]);        }    }    long long ans=0;    for(int i=1;i<=tot;i++)        for(int j=l[i],w=heap[root[i]].w;j<=r[i];j++)            ans+=abs(t[j]-w);    cout<