#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define INF 1023456789
#define LINF 1023456789123456789
#define lb(x,v) lower_bound(all(x),v)-x.begin()
#define disc(x) sort(all(x)),x.resize(unique(all(x))-x.begin())
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> li;
#define maxn 500005
struct node{
int s,e,m,lz;ii v;
node *l,*r;
node(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1,lz=0;v={1,s};
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void ppo(){
v.se+=lz;
if(s!=e)l->lz+=lz,r->lz+=lz;
lz=0;
}
void add(int x,int y,int nv){
if(s==x&&e==y){lz+=nv;return;}
if(y<=m)l->add(x,y,nv);
else if(x>m)r->add(x,y,nv);
else l->add(x,m,nv),r->add(m+1,y,nv);
l->ppo(),r->ppo();
v=min(l->v,r->v);
}
inline void flip(int x){
if(s==x&&e==x){v.fi=1-v.fi;return;}
if(x<=m)l->flip(x);
else r->flip(x);
l->ppo(),r->ppo();
v=min(l->v,r->v);
}
ii qry(int x,int y){
ppo();
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
else if(x>m)return r->qry(x,y);
else return min(l->qry(x,m),r->qry(m+1,y));
}
}*rt;
int n,a[maxn],l[maxn],r[maxn],pos[maxn];
vector<ii> cyc[maxn],stuff;
int dbg=0;
int md;
int n=30,m=100,s=5;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main(){
if(rng()%2)md=-1;
else md=1;
sf("%d",&n);
for(int i=0;i<n;++i)sf("%d",&a[i]);
l[0]=(a[0]==-1)?0:-1;
for(int i=1;i<n;++i){
if(a[i]==-1)l[i]=i;
else l[i]=l[i-1];
}
r[n-1]=(a[n-1]==-1)?n-1:n;
for(int i=n-2;i>=0;--i){
if(a[i]==-1)r[i]=i;
else r[i]=r[i+1];
}
for(int i=0;i<n;++i){
if(a[i]>0){
int d=(r[i]==n?INF:r[i])-i;
if(l[i]!=-1)d=min(d,i-l[i]);
cyc[r[i]].pb({d,md*i});
}
}
rt=new node(0,n-1);
for(int i=0;i<=n;++i){
if(cyc[i].empty())continue;
sort(all(cyc[i]));
int x=md*cyc[i].back().se;
--a[x];
pos[i]=x;
//need to reach here at x time
rt->flip(x);
if(dbg)pf("walk: %d\n",x);
}
for(int i=0;i<n;++i){
if(a[i]>0){
int d=INF;
if(l[i]!=-1)d=min(d,i-l[i]);
d=min(d,(r[i]==n?INF:r[i])-i);
stuff.pb({d,i});
}
}
sort(all(stuff));
for(auto[d,i]:stuff){
int num=a[i];
ii mn=rt->qry(i,n-1);
if(mn.fi!=1)num=min(num,mn.se/(2*d));
if(dbg)pf("d: %d\n",d);
if(dbg)pf("mn: %d %d\n",mn.fi,mn.se);
int rem=rt->qry(i,i).se;
int cur=rem/(2*d);
if(rem>=0&&i<pos[r[i]])++cur;
if(dbg)pf("rem %d, cur %d, %d %d\n",rem,cur,i,pos[r[i]]);
num=min(num,cur);
if(dbg)pf("take %d of %d\n\n",num,i);
a[i]-=num;
if(num>0){
if(i!=pos[r[i]])rt->flip(i);
rt->add(i,n-1,-num*d*2);
}
}
ll ans=0;
for(int i=0;i<n;++i){
if(a[i]>0)ans+=a[i];
}
pf("%lld\n",ans);
}
/*
5
-1 1 1 1 1
2
8
-1 1 0 0 -1 0 0 3
1
8
2 -1 2 -1 2 -1 2 -1
1
5
-1 -1 3 3 3
*/
Compilation message
tortoise.cpp:63:5: error: redefinition of 'int n'
63 | int n=30,m=100,s=5;
| ^
tortoise.cpp:57:5: note: 'int n' previously declared here
57 | int n,a[maxn],l[maxn],r[maxn],pos[maxn];
| ^
tortoise.cpp: In function 'int main()':
tortoise.cpp:69:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | sf("%d",&n);
| ^
tortoise.cpp:70:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | for(int i=0;i<n;++i)sf("%d",&a[i]);
| ^
