#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
int N;
ll sum,ans;
ll arr[1000001];
ll lc[1000001], rc[1000001];
ll grp[1000001], grpsum[1000001] , grpnow;
set<array<ll,3> > pq;
set<ll> bar;
set<ll> S, nS;
struct Seg{
ll arr[4000001];
ll lazy[4000001];
void propagate(int now, int s, int e){
arr[now] += lazy[now];
if(s!=e){ lazy[now*2]+=lazy[now]; lazy[now*2+1]+=lazy[now];}
lazy[now] = 0;
}
void update(int now, int s, int e, int l, int r, ll x){
if(l>r) return;
propagate(now,s,e);
if(l<=s && e<=r){
arr[now] += x;
if(s!=e){ lazy[now*2]+=x; lazy[now*2+1]+=x;}
return;
}
if(l>e || r<s) return;
int m = s+e>>1;
update(now*2,s,m,l,r,x); update(now*2+1,m+1,e,l,r,x);
arr[now] = min(arr[now*2],arr[now*2+1]);
}
ll query(int now, int s, int e, int l, int r){
if(l>r) return 2*inf;
propagate(now,s,e);
if(l<=s && e<=r) return arr[now];
if(l>e || r<s) return 2*inf;
int m = s+e>>1;
return min(query(now*2,s,m,l,r) , query(now*2+1,m+1,e,l,r));
}
} seg;
int main(){
IO
cin>>N;
forf(i,1,N) cin>>arr[i];
forf(i,1,N) seg.update(1,1,N,i,i,inf+i-1);
arr[N+1] = -1;
forf(i,1,N) if(arr[i] > 0) sum += arr[i];
forf(i,1,N+1){
if(arr[i] != -1) continue;
if(i != N+1) bar.insert(i);
int now = i-1;
while(now >= 1 && arr[now] == 0) now--;
if(now == 0 || arr[now] == -1) continue;
arr[now]--; ans++; S.insert(now); seg.update(1,1,N,now,now,-inf);
if(i != N+1) pq.insert({(i-now)*2, 1, now});
grpnow++;
while(now >= 1 && arr[now] >= 0) now--;
forf(j, now+1, i-1) grp[j] = grpnow;
}
forf(i,1,N) if(arr[i] > 0) grpsum[grp[i]] += arr[i], nS.insert(i);
forf(i,1,N){
if(arr[i] > 0){
lc[i] = inf, rc[i] = inf;
if(bar.upper_bound(i) != bar.begin()) lc[i] = i - *prev(bar.upper_bound(i));
if(bar.upper_bound(i) != bar.end()) rc[i] = *bar.upper_bound(i) - i;
if(lc[i] < rc[i]) pq.insert({lc[i]*2, 0, i});
else pq.insert({rc[i]*2, 1, i});
}
}
while(sz(pq)){
auto [v,c,i] = *pq.begin(); pq.erase(pq.begin());
if(grpsum[grp[i]] == 0) continue;
if(c == 0){
int fst = 1;
if(S.find(i) != S.end()) fst = 0;
if(fst) seg.update(1,1,N,i,i,-inf);
seg.update(1,1,N,i+fst,N,-v);
if(seg.query(1,1,N,1,N) < 0){
if(fst) seg.update(1,1,N,i,i,inf);
seg.update(1,1,N,i+fst,N,v);
continue;
}
S.insert(i); arr[i]--; ans++; grpsum[grp[i]]--;
if(arr[i]) pq.insert({lc[i]*2, 0, i});
else nS.erase(i);
}
else{
ll prv = *prev(nS.upper_bound(i));
int fst = 1;
if(S.find(prv) != S.end()) fst = 0;
if(fst) seg.update(1,1,N,prv,prv,-inf);
seg.update(1,1,N,i,N,-v);
if(seg.query(1,1,N,1,N) < 0){
if(fst) seg.update(1,1,N,prv,prv,inf);
seg.update(1,1,N,i,N,v);
continue;
}
S.insert(prv); arr[prv]--; ans++; grpsum[grp[prv]]--;
if(arr[prv] == 0) nS.erase(prv);
if(prv == i) pq.insert({rc[i]*2, 1, i});
}
}
cout<<sum-ans;
}
