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

 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1000005; 4 typedef long long ll; 5 int read(){ 6     int rt=0,fl=1;char ch=getchar(); 7     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)fl=-1;ch=getchar();} 8     while(ch>=‘0‘&&ch<=‘9‘){rt=rt*10+ch-‘0‘;ch=getchar();} 9     return rt*fl;10 }11 ll ans;12 int n,now;13 int a[maxn],root[maxn];14 int L[maxn],R[maxn],tot[maxn];15 struct Tr{16     int cnt;17     int l[maxn],r[maxn];18     ll v[maxn];int sz[maxn],d[maxn];19     int merge(int x,int y){20         if(x==0||y==0)return x+y;21         if(v[x]<v[y])swap(x,y);22         r[x]=merge(r[x],y);23         sz[x]=sz[l[x]]+sz[r[x]]+1;24         if(d[r[x]]>d[l[x]])swap(l[x],r[x]);25         d[x]=d[r[x]]+1;26         return x;27     }28     int top(int x){29         return v[x];30     }31     int size(int x){32         return sz[x];33     }34     void pop(int &x){35         x=merge(l[x],r[x]);36     }37     int Create(ll x){38         v[++cnt]=x;39         sz[cnt]=1;40         l[cnt]=r[cnt]=d[cnt]=0;41         return cnt;42     }43 }heap;44 int main(){45     n=read();46     for(int i=1;i<=n;i++)a[i]=read()-i;47     for(int i=1;i<=n;i++){48         now++;49         root[now]=heap.Create(a[i]);50         tot[now]=1;51         L[now]=R[now]=i;52         while(now>1 && heap.top(root[now-1])>heap.top(root[now])){53             now--;54             root[now]=heap.merge(root[now+1],root[now]);55             tot[now]+=tot[now+1];R[now]=R[now+1];56             while(heap.size(root[now])*2>tot[now]+1)57                 heap.pop(root[now]);58         }59     }60     for(int i=1;i<=now;i++)61         for(int j=L[i],t=heap.top(root[i]);j<=R[i];j++)62             ans+=abs(a[j]-t);63     printf("%lld",ans);64 }