#include <bits/stdc++.h>
using namespace std;
const int nmax = 5e5;
struct candy
{
int poz, to, val;
};
int n;
int v[nmax + 5];
int st[nmax + 5], dr[nmax + 5];
vector<candy> l;
void debug(vector<candy> a)
{
for(auto it : a)
{
cerr<<it.poz<<' '<<it.to<<' '<<it.val<<'\n';
}
cerr<<'\n';
}
bool can_add(int poz, int to)
{
//debug(l);
if(!v[poz])
{
return false;
}
if(poz >= l.back().poz)
{
if(to < l.back().to)
{
return false;
}
if(l.back().val + abs(l.back().poz - l.back().to) + abs(l.back().to - poz) <= 2 * (poz - 1))
{
return true;
}
return false;
}
int poz_l = 0;
for(int i=1;i<l.size();i++)
{
if(l[i].poz <= poz)
{
poz_l = i;
}
else
{
break;
}
}
if(l[poz_l].to > to)
{
return false;
}
if(l[poz_l + 1].to < to)
{
return false;
}
int Min = l[poz_l].val + abs(l[poz_l].poz - l[poz_l].to) + abs(l[poz_l].to - poz);
if(dr[l[poz_l].poz] != 0)
{
Min = min(Min, l[poz_l].val + abs(l[poz_l].poz - dr[l[poz_l].poz]) + abs(dr[l[poz_l].poz] - poz));
}
if(st[l[poz_l].poz] != 0)
{
Min = min(Min, l[poz_l].val + abs(l[poz_l].poz - st[l[poz_l].poz]) + abs(st[l[poz_l].poz] - poz));
}
if(Min > 2 * (poz - 1))
{
return false;
}
int dif = 0;
if(Min == l[poz_l].val + abs(l[poz_l].poz - l[poz_l].to) + abs(l[poz_l].to - poz))
{
dif += abs(poz - l[poz_l].to);
dif += abs(l[poz_l + 1].poz - to);
dif += abs(poz - to);
dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
}
else if(dr[l[poz_l].poz] != 0 && Min == l[poz_l].val + abs(l[poz_l].poz - dr[l[poz_l].poz]) + abs(dr[l[poz_l].poz] - poz))
{
dif += abs(dr[l[poz_l].poz] - poz);
dif += abs(l[poz_l + 1].poz - to);
dif += abs(poz - to);
dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
dif -= abs(l[poz_l].poz - l[poz_l].to);
dif += abs(l[poz_l].poz - dr[l[poz_l].poz]);
}
else
{
dif += abs(st[l[poz_l].poz] - poz);
dif += abs(l[poz_l + 1].poz - to);
dif += abs(poz - to);
dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
dif -= abs(l[poz_l].poz - l[poz_l].to);
dif += abs(l[poz_l].poz - st[l[poz_l].poz]);
}
for(int i=poz_l+1;i<l.size();i++)
{
if(l[i].val + dif > 2 * (l[i].poz - 1))
{
return false;
}
}
return true;
}
void add(int poz, int to)
{
int poz_l = 0;
for(int i=1;i<l.size();i++)
{
if(l[i].poz <= poz)
{
poz_l = i;
}
else
{
break;
}
}
int Min = l[poz_l].val + abs(l[poz_l].poz - l[poz_l].to) + abs(l[poz_l].to - poz);
if(dr[l[poz_l].poz] != 0)
{
Min = min(Min, l[poz_l].val + abs(l[poz_l].poz - dr[l[poz_l].poz]) + abs(dr[l[poz_l].poz] - poz));
}
if(st[l[poz_l].poz] != 0)
{
Min = min(Min, l[poz_l].val + abs(l[poz_l].poz - st[l[poz_l].poz]) + abs(st[l[poz_l].poz] - poz));
}
int dif = 0;
if(Min == l[poz_l].val + abs(l[poz_l].poz - l[poz_l].to) + abs(l[poz_l].to - poz))
{
dif += abs(poz - l[poz_l].to);
dif += abs(l[poz_l + 1].poz - to);
dif += abs(poz - to);
dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
}
else if(dr[l[poz_l].poz] != 0 && Min == l[poz_l].val + abs(l[poz_l].poz - dr[l[poz_l].poz]) + abs(dr[l[poz_l].poz] - poz))
{
dif += abs(dr[l[poz_l].poz] - poz);
dif += abs(l[poz_l + 1].poz - to);
dif += abs(poz - to);
dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
dif -= abs(l[poz_l].poz - l[poz_l].to);
dif += abs(l[poz_l].poz - dr[l[poz_l].poz]);
l[poz_l].to = dr[l[poz_l].poz];
}
else
{
dif += abs(st[l[poz_l].poz] - poz);
dif += abs(l[poz_l + 1].poz - to);
dif += abs(poz - to);
dif -= abs(l[poz_l + 1].poz - l[poz_l].to);
dif -= abs(l[poz_l].poz - l[poz_l].to);
dif += abs(l[poz_l].poz - st[l[poz_l].poz]);
l[poz_l].to = st[l[poz_l].poz];
}
vector<candy> aux;
for(int i=0;i<=poz_l;i++)
{
aux.push_back(l[i]);
}
aux.push_back({poz, to, Min});
for(int i=poz_l+1;i<l.size();i++)
{
aux.push_back({l[i].poz, l[i].to, l[i].val + dif});
}
l = aux;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef home
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
#endif // home
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i];
}
for(int i=1;i<=n;i++)
{
if(v[i] == -1)
{
st[i] = i;
continue;
}
st[i] = st[i - 1];
}
for(int i=n;i>=1;i--)
{
if(v[i] == -1)
{
dr[i] = i;
continue;
}
dr[i] = dr[i + 1];
}
vector<pair<int,pair<int,int>>> c;
for(int i=1;i<=n;i++)
{
if(v[i] < 1)
{
continue;
}
if(st[i] != 0)
{
c.push_back({i - st[i], {i, st[i]}});
}
if(dr[i] != 0)
{
c.push_back({dr[i] - i, {i, dr[i]}});
}
}
sort(c.begin(), c.end());
l.push_back({1, 1, 0});
for(auto it : c)
{
int poz = it.second.first;
int to = it.second.second;
while(can_add(poz, to))
{
--v[poz];
add(poz, to);
}
}
int rez = 0;
for(int i=1;i<=n;i++)
{
if(v[i] == -1)
{
continue;
}
rez += v[i];
}
cout<<rez<<'\n';
return 0;
}
