#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=35000+3;
int n,a[N],b[N],c[N],cnt,s[N],ans,tot,answer,first[N];
ll sumL[N],sumR[N];
ll f[N];
vector<int> G;
bool vis[100005];
struct zjy
{
  int id,w;
  bool operator < (zjy t) const{
  return w<t.w;
  }
};
ll Abs(ll x)
{
  if(x>0)
  {
    return x;
  }
  else
  {
    return -x;
  }
}
signed main()
{
  scanf("%d",&n);
  for(register int i=1;i<=n;++i)
  {
    scanf("%d",&a[i]);
    b[i]=a[i]-i;
  }
  priority_queue<zjy> q;
  q.push((zjy){0,0});
  for(register int i=1;i<=n;++i)
  {
    while(b[q.top().id]>b[i]&&(!q.empty()))
    {
      c[++cnt]=q.top().id;
      q.pop();
    }
    if(!q.empty())
    {
      s[i]=s[q.top().id]+1;
    }
    else
    {
      s[i]=1;
    }
    ans=max(ans,s[i]);
    for(int j=cnt;j>=1;--j)
    {
      
      q.push((zjy){c[j],s[c[j]]});
    }
    q.push((zjy){i,s[i]});
    cnt=0;
  }
  cout<<n-ans<<endl;
  while(!q.empty())
  {
    G.push_back(q.top().id);
    if(!vis[q.top().w])
    {
     first[q.top().w]=G.size()-1;
     vis[q.top().w]=1; 
    }
    q.pop();
  }
  int last=n+1; 
  b[last]=1e9;
  s[last]=ans+1;
  cnt=0;
  memset(f,0x3f3f,sizeof(f));
  f[0]=0ll;
  b[0]=-1e9;
  for(register int i=1;i<=n+1;++i)
  {
    for(register int j=first[s[i]-1];j<G.size();++j)
    {
      if(b[G[j]]>b[i]||G[j]>i)
      {
        continue;
      }
      if(s[G[j]]!=s[i]-1)
      {
        break;
      }
      int u=G[j];
 //     cout<<u<<" "<<s[i]<<" "<<i<<" ";
      sumL[u]=0;
      for(register int k=u+1;k<i;++k)
      {
        sumL[k]=sumL[k-1]+Abs((ll)(b[k]-b[u]));
   //     cout<<sumL[k]<<" ";
      }
    //  cout<<" ";
      sumR[i-1]=0;
      for(register int k=i-2;k>=u;--k)
      {
        sumR[k]=sumR[k+1]+Abs((ll)(b[k+1]-b[i]));
    //    cout<<sumR[k]<<" ";
      }
      for(register int k=u;k<i;++k)
      {
        f[i]=min(f[i],f[u]+sumL[k]+sumR[k]);
      }
  //    cout<<f[i]<<endl;
    }
  }
  printf("%lld",f[n+1]);
  return 0;
}