#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 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 inf;
propagate(now,s,e);
if(l<=s && e<=r) return arr[now];
if(l>e || r<s) return 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);
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--;
grpnow++;
forf(j, now + 1, i - 1) grp[j] = grpnow;
}
forf(i, 1, N) if (arr[i] > 0) nS.insert(i), grpsum[grp[i]] += arr[i];
forf(i, 1, N) {
if (arr[i] != -1) continue;
if (nS.lower_bound(i) != nS.end()) {
ll nxt = *nS.lower_bound(i);
if (bar.upper_bound(i) == bar.end() || nxt < *bar.upper_bound(i)) pq.insert({2 * (nxt - i), -nxt, 0});
}
if (nS.lower_bound(i) != nS.begin()) {
ll prv = *prev(nS.lower_bound(i));
if (bar.lower_bound(i) == bar.begin() || prv > *prev(bar.lower_bound(i))) {
S.insert(prv); arr[prv]--; grpsum[grp[prv]]--; ans++; if (arr[prv] == 0) nS.erase(prv);
seg.update(1,1,N,prv,prv,-inf);
pq.insert({2 * (i - prv), -prv, 1});
}
}
}
if(sz(nS)){
ll prv = *prev(nS.lower_bound(N+1));
if (bar.lower_bound(N+1) == bar.begin() || prv > *prev(bar.lower_bound(N+1))) {
S.insert(prv); arr[prv]--; ans++; grpsum[grp[prv]]--; if (arr[prv] == 0) nS.erase(prv);
seg.update(1,1,N,prv,prv,-inf);
}
}
while(sz(pq)){
auto [v,i,c] = *pq.begin(); pq.erase(pq.begin());
i *= -1;
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] == 0) nS.erase(i);
if(nS.lower_bound(i) == nS.end()) continue;
ll nxt = *nS.lower_bound(i);
if(bar.lower_bound(i) == bar.end() || nxt < *bar.lower_bound(i)){
pq.insert({2*(nxt - *prev(bar.lower_bound(i))), -nxt, 0});
}
}
else{
ll prv = *prev(nS.upper_bound(i));
if(!(bar.lower_bound(i) == bar.begin() || prv > *prev(bar.lower_bound(i)))) continue;
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);
pq.insert({2*(*bar.lower_bound(i) - prv), -prv, 1});
}
}
cout<<sum-ans;
}
