#include <bits/stdc++.h>
using namespace std;
bool comp(pair<int, int> a, pair<int, int> b) {
  return (a.first == b.first) ? a.second > b.second : a.first > b.first;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  long long int arr[n];
  for (int i = 0; i < n; i++) cin >> arr[i];
  long long int cost[n];
  long long int height[n];
  for (int i = 0; i < n; i++) cost[i] = (1100000000);
  cost[0] = 0;
  height[0] = arr[0];
  long long int apCost[n][n], apHeight[n][n], apMedian[n][n];
  for (int i = 0; i < n; i++) {
    set<pair<int, int>, bool (*)(pair<int, int>, pair<int, int>)> heap1(comp);
    set<pair<int, int> > heap2;
    long long int sum1 = 0, sum2 = 0;
    for (int j = i; j < n; j++) {
      int elem = arr[j] - (j - i);
      if (heap1.size() == 0 || elem <= heap1.begin()->first) {
        heap1.insert(make_pair(elem, j));
        sum1 += elem;
        if (heap1.size() > (heap2.size() + 1)) {
          pair<int, int> del = *heap1.begin();
          heap1.erase(del);
          sum1 -= del.first;
          heap2.insert(del);
          sum2 += del.first;
        }
      } else {
        heap2.insert(make_pair(elem, j));
        sum2 += elem;
        if (heap2.size() > heap1.size()) {
          pair<int, int> del = *heap2.begin();
          heap2.erase(del);
          sum2 -= del.first;
          heap1.insert(del);
          sum1 += del.first;
        }
      }
      long long int norm = heap1.begin()->first;
      apMedian[i][j] = norm;
      apCost[i][j] = heap1.size() * norm - sum1 + sum2 - heap2.size() * norm;
      apHeight[i][j] = (norm) + (j - i);
    }
  }
  for (int i = 1; i < n; i++) {
    set<pair<int, int> > minHeap, maxHeap;
    cost[i] = apCost[0][i];
    height[i] = apHeight[0][i];
    for (int j = i - 1; j >= 0; j--) {
      if (apMedian[j + 1][i] > height[j]) {
        if (cost[j] + apCost[j + 1][i] < cost[i]) {
          cost[i] = cost[j] + apCost[j + 1][i];
          height[i] = apHeight[j + 1][i];
        } else if (cost[j] + apCost[j + 1][i] == cost[i]) {
          height[i] = min(height[i], apHeight[j + 1][i]);
        }
      }
    }
  }
  cout << cost[n - 1];
  return 0;
}
