rt，除了#2，全WA。

#include<bits/stdc++.h>
using namespace std;
long long n,a[35005]={-10000000000},dp[35005],trans[35005],lis[35005]={-1},lislen=0,total_ans=0x3f3f3f3f3f3f3f3f;
long long absolute(long long x) {
    if (x<0) return -x;
    return x;
}
int main() {
    scanf("%lld",&n);
    a[++n]=10000000000;
    for (long long i=1;i<n;i++) {
        scanf("%lld",&a[i]);
        a[i]-=i;
        dp[i]=1;
    }
    for (long long i=0;i<=n;i++) {
        if (lislen==0||a[i]>=a[lis[lislen]]) {
            trans[i]=lis[lislen];
            lis[++lislen]=i;
        }
        else {
            long long l=1,r=lislen,mid=0,ans=-1;
            while (l<=r) {
                mid=l+r>>1;
                if (a[i]<a[lis[mid]]) {
                    ans=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            trans[i]=lis[ans-1];
            lis[ans]=i;
        }
        dp[i]=lislen;
    }
    for (long long k=1;k<n;k++) {
        if (dp[k]==lislen-1) {
            long long ans=0;
            lis[lislen-1]=k;
            for (long long i=lislen-2;i>1;i--) lis[i]=trans[lis[i+1]];
            for (long long i=1;i<lislen;i++) {
                long long sum=0,minn=0x3f3f3f3f3f3f3f3f;
                for (long long j=lis[i]+1;j<lis[i+1];j++) sum+=absolute(a[j]-a[lis[i+1]]);
                minn=sum;
                for (long long j=lis[i]+1;j<lis[i+1];j++)  {
                    sum=sum-absolute(a[j]-a[lis[i+1]])+absolute(a[j]-a[lis[i]]);
                    minn=min(minn,sum);
                }
                ans+=minn;
            }
            total_ans=min(total_ans,ans);
        }
    }
    printf("%lld\n%lld",n+1-lislen,total_ans);
    return 0;
}