#include <bits/stdc++.h>
using namespace std;
#define int long long
#define str string
struct SegTree {
int size = 1;
vector<int> adds;
SegTree (int n){
while(size < n)
size <<= 1;
adds.resize(size << 1);
}
void add(int l, int r, int v, int x, int lx, int rx){
if(l <= lx and rx <= r){
adds[x] += v;
return;
}
if(rx <= l or r <= lx)
return;
int m = (lx + rx) >> 1;
add(l, r, v, (x << 1) + 1, lx, m);
add(l, r, v, (x << 1) + 2, m, rx);
}
void add(int l, int r, int x){
add(l, r, x, 0, 0, size);
}
int get(int n, int x, int lx, int rx){
if(lx + 1 == rx)
return adds[x];
int mid = (lx + rx) >> 1;
if(n < mid)
return get(n, (x << 1) + 1, lx, mid) + adds[x];
else
return get(n, (x << 1) + 2, mid, rx) + adds[x];
}
int get(int i){
return get(i, 0, 0, size);
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; i ++)
cin >> a[i];
int left = 0, right = n - 1;
int ans = 0;
SegTree s(n);
for(int i = 0; i < n; i ++)
s.add(i, i + 1, a[i]);
while(left < right){
while(left + 1 < n and s.get(left) < s.get(left + 1))
left ++;
while(right - 1 >= 0 and s.get(right - 1) > s.get(right))
right --;
if(left < right){
if(left + 1 == right and s.get(left) == s.get(right)){
ans ++;
break;
}
int x = s.get(left) - s.get(left + 1) + 1, y = s.get(right) - s.get(right - 1) + 1;
if(x <= y)
ans += x, s.add(left + 1, right, x);
else
ans += y, s.add(left + 1, right, y);
}
else
break;
}
cout << ans;
}
