#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 35005
#define inf 12345678987654
#define ll long long
using namespace std;
int n,len,tot,a[N],d[N],g[N];
ll b[N],f[N],sump[N],sums[N];
struct node{int to,next,head;}edg[1000005];
void add(int x,int y) {edg[++tot].to=y;edg[tot].next=edg[x].head;edg[x].head=tot;}
ll Abs(ll x) {return x>=0?x:-x;}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	for (int i=1;i<=n;++i)
		b[i]=a[i]-i;
	b[0]=-inf;b[n+1]=inf;
	d[1]=b[1];len=1;
	for (int i=2;i<=n+1;++i)
	{
		if (b[i]>=d[len]) d[++len]=b[i],g[i]=len;
		else
		{
			int j=upper_bound(d+1,d+len+1,b[i])-d;
			d[j]=b[i];g[i]=j;
		}
		add(g[i],i);
	}
	add(0,0);
	printf("%d\n",n-len+1);
	for (int i=1;i<=n+1;++i)
		f[i]=inf;
	for (int i=1;i<=n+1;++i)
	{
		for (int j=edg[g[i]-1].head;j;j=edg[j].next)
		{
			int pre=edg[j].to;
			if (pre>i||b[pre]>b[i]) continue;
			sump[pre]=sums[i-1]=0;
			for (int k=pre+1;k<=i-1;++k)
				sump[k]=sump[k-1]+Abs(b[k]-b[pre]);
			for (int k=i-2;k>=pre;--k)
				sums[k]=sums[k+1]+Abs(b[k+1]-b[i]);
			for (int k=pre;k<=i-1;++k)
				f[i]=min(f[i],f[pre]+sump[k]+sums[k]);
		}
	}
	printf("%lld\n",f[n+1]);
	return 0;
}