#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define pi pair<int, int>
#define f first
#define s second
#define V vector
const int inf=1e9;
int wyn=0, licznik=0, suma_czasow=0, n;
priority_queue<pi> pq;
void wrzuc(int czas, int ile) {
if(ile<=0) return;
suma_czasow+=czas*ile;
licznik+=ile;
pq.push({czas, ile});
}
void wywal(int fosy) {
auto [czas, ile] = pq.top();
suma_czasow-=czas*ile;
licznik-=ile;
pq.pop();
if(suma_czasow>=fosy) return;
int ilen = (fosy-suma_czasow)/czas;
wrzuc(czas, ilen);
}
signed main() {
cin.tie(0) -> ios_base::sync_with_stdio(0);
cin >> n;
V<int> A(n+1), lewo(n+1), prawo(n+1), niezerowy(n+1);
FOR(i, 1, n) cin >> A[i];
int sum=0;
int idxl=-inf, idxp=inf, idxn=inf;
FOR(i, 1, n) {
if(A[i]>0) sum+=A[i];
lewo[i]=idxl;
if(A[i]==-1) idxl=i;
}
for(int i=n; i>=1; --i) {
prawo[i]=idxp;
niezerowy[i]=idxn;
if(A[i]==-1) idxp=i;
if(A[i]>0) idxn=i;
}
FOR(i, 1, n) {
if(A[i]<=0) continue;
int spacer = inf;
if(niezerowy[i]<=n && prawo[i]<=n) spacer=max(0ll, prawo[i]-niezerowy[i]);
wrzuc(2*min(prawo[i]-i, i-lewo[i]), A[i]-1);
wrzuc(2*min({spacer, prawo[i]-i, i-lewo[i]}), 1);
int fosy=i+2*min({spacer, prawo[i]-i, i-lewo[i]});
while(suma_czasow>fosy) wywal(fosy);
wyn=max(wyn, licznik);
}
cout << sum-wyn << '\n';
}
