// author: erray
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(37)
#endif
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<int> A(N + 1);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
vector<long long> cost(N + 1);
cost[N] = 0;
for (int i = N - 1; i >= 0; --i) {
cost[i] = cost[i + 1] + max(0, A[i + 1] - A[i] + 1);
}
debug(cost);
long long ans = (long long) 1e17;
long long sum = 0;
for (int i = 0; i < N; ++i) {
if (i > 1) {
sum += max(0, A[i - 2] - A[i - 1] + 1);
}
ans = min(ans, max(sum, cost[i + 1]) + max({A[i + 1] - A[i] + 1, (i == 0 ? 0 : A[i - 1]) - A[i] + 1, 0}));
}
cout << ans << '\n';
}
