#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int IINF = INT_MAX;
const char EMPTY = 'X';
 
struct Node{
  int value;
  /*
    lazy : 
    A : 加算の遅延 ( ADD )
    S : 区間の要素を指定した値にする遅延 ( SET )

    lazy_coef : 
    区間にいくら加算するのかor何をセットするのかを記録
   */
  char lazy;
  int lazy_coef; 
  Node(int value=0,char lazy=EMPTY,int lazy_coef=0):value(value),lazy(lazy),lazy_coef(lazy_coef){}
};
 
class MixSegmentTree{
public:
  vector<Node> RMQ;
  vector<int> minimum_dat,maximum_dat;
  int limit,N; // N は要素数
 
  void init(int tmp){
    N = tmp;
    int N_N = 1;
    while(N_N < N)N_N *= 2;
    limit = N_N;
    RMQ.resize(3*limit);
    minimum_dat.resize(3*limit);
    maximum_dat.resize(3*limit);
    rep(i,3*limit-1) {
      RMQ[i] = Node();
      minimum_dat[i] =  IINF;
      maximum_dat[i] = -IINF;
    }
  }

  /* 
  O(n)でRMQを初期化
  [L,R)
  tuple<int,int,int>(総和、最小値、最大値)
  */
  tuple<int,int,int> _build(int cur,int L,int R,const vector<int> &buf){

    if( !( 0 <= cur && cur < 2*limit-1 ) ) return tuple<int,int,int>(0,IINF,-IINF);
    if( L == R-1 ){
      if( L >= N ) return tuple<int,int,int>(0,IINF,-IINF);
      //各要素の値が一定でない場合 ( 配列に初期値をいれてそれで初期化する場合 )
      //buf[] を用意し値を入れ RMQ[cur].value = buf[L]; とする
      // RMQのL番目の要素をbuf[L]で更新
      RMQ[cur].value = buf[L];
      minimum_dat[cur] = buf[L];
      maximum_dat[cur] = buf[L];
      //各要素が全て同じの場合
      //RMQ[cur] = 0; // RMQ の各要素を０で初期化、 1 なら RMQ[cur] = 1などなど...
      //minimum_dat[cur] = 0;
      //maximum_dat[cur] = 0;
    } else {
      tuple<int,int,int> vl = _build(cur*2+1,L,(L+R)/2,buf);
      tuple<int,int,int> vr = _build(cur*2+2,(L+R)/2,R,buf);
      RMQ[cur].value = get<0>(vl) + get<0>(vr);
      minimum_dat[cur] = min(get<1>(vl),get<1>(vr));
      maximum_dat[cur] = max(get<2>(vl),get<2>(vr));
    }
    return tuple<int,int,int>(RMQ[cur].value,minimum_dat[cur],maximum_dat[cur]);
  }

  //initしてから使用すること!!! でないとlimitに正しい値が入っていません
  void build(const vector<int> &buf) { _build(0,0,limit,buf); }

  inline void value_evaluate(int index,int L,int R){
    if( RMQ[index].lazy == 'A' ){
      RMQ[index].value += ( R - L ) * RMQ[index].lazy_coef;
      minimum_dat[index] += RMQ[index].lazy_coef;
      maximum_dat[index] += RMQ[index].lazy_coef;
    } else if( RMQ[index].lazy == 'S' ){
      RMQ[index].value = ( R - L ) * RMQ[index].lazy_coef;
      minimum_dat[index] = RMQ[index].lazy_coef;
      maximum_dat[index] = RMQ[index].lazy_coef;
    }
  }
   
  inline void lazy_evaluate(int index,int L,int R){
    value_evaluate(index,L,R);
    if( index < limit && RMQ[index].lazy != EMPTY ) {
      if( RMQ[index].lazy == 'A' ) {
        if( RMQ[index*2+1].lazy == EMPTY ) RMQ[index*2+1].lazy = 'A'; 
        if( RMQ[index*2+2].lazy == EMPTY ) RMQ[index*2+2].lazy = 'A';
        RMQ[index*2+1].lazy_coef += RMQ[index].lazy_coef;
        RMQ[index*2+2].lazy_coef += RMQ[index].lazy_coef;
      } else if( RMQ[index].lazy == 'S') {
        RMQ[index*2+1].lazy = RMQ[index*2+2].lazy = 'S';
        RMQ[index*2+1].lazy_coef = RMQ[index].lazy_coef;
        RMQ[index*2+2].lazy_coef = RMQ[index].lazy_coef;
      }
    }
    RMQ[index].lazy = EMPTY;
    RMQ[index].lazy_coef = 0;
  }
 
  inline void value_update(int index){
    RMQ[index].value = RMQ[index*2+1].value + RMQ[index*2+2].value;
    minimum_dat[index] = min(minimum_dat[index*2+1],minimum_dat[index*2+2]);
    maximum_dat[index] = max(maximum_dat[index*2+1],maximum_dat[index*2+2]);
  }
 
  /*
  //[a,b)に対して、oprを行う
  今みてるレンジ[L,R)
  [a,b)の各要素に対して、
  opr が 'A'ならvを加算 ( ADD )
  opr が 'S'ならvに置換 ( SET )
  */
  void _update(int a,int b,char opr,int v,int index,int L,int R){
    /*
      RMQ[index].lazy にEMPTY以外の値がセットされているのであれば
      その遅延を子ノードに伝える
    */
    lazy_evaluate(index,L,R);
 
    if( b <= L || R <= a )return;
    if( a <= L && R <= b ){
      /*
        [L,R)が目的の範囲に入ったので、ここで処理を終える ( 今いるノードは更新するが子は更新しない, その代わり遅延を残しておく )
        [今いるノード]            [今いるノード]
        [子供]  [子供]     => [子供,遅延] [子供,遅延]
        子供の値は変化しない
        後にその子供を訪れた際に遅延を見て処理を行う
      */
      RMQ[index].lazy = opr; // 今いるノードに遅延を設定して処理をしてもらう
      if( opr == 'A' )      RMQ[index].lazy_coef += v; 
      else if( opr == 'S' ) RMQ[index].lazy_coef = v; 
      lazy_evaluate(index,L,R);
      return;
    }
 
    _update(a,b,opr,v,index*2+1,L,(L+R)/2);
    _update(a,b,opr,v,index*2+2,(L+R)/2,R);
    value_update(index);
 
  }

  // [a,b) に対して opr を行う
  void update(int a,int b,char opr,int v){ _update(a,b,opr,v,0,0,limit); } 

  tuple<int,int,int> _query(int a,int b,int index,int L,int R){
    lazy_evaluate(index,L,R); //子ノードにまだ正しい値が入っていない(遅延している)可能性があるので評価して正しい値を入れる
 
    if( b <= L || R <= a ) return make_tuple(0,IINF,-IINF);
    if( a <= L && R <= b ) return make_tuple(RMQ[index].value,minimum_dat[index],maximum_dat[index]);


    auto tmp1 = _query(a,b,index*2+1,L,(L+R)/2);
    auto tmp2 = _query(a,b,index*2+2,(L+R)/2,R);
    tuple<int,int,int> ret = make_tuple(get<0>(tmp1)+get<0>(tmp2),min(get<1>(tmp1),get<1>(tmp2)),max(get<2>(tmp1),get<2>(tmp2)));
    value_update(index); //ここまでくると子の値が正しくなっているのでその和をとって今いるノードにも正しい値をいれる
    return ret;
  }

  // [a,b) の総和、最小値、最大値を返す
  tuple<int,int,int> query(int a,int b) { return _query(a,b,0,0,limit); }

};



const int MAX_V = 100010;
const int MINI_IINF = 500000;
int W,arr[MAX_V];

void compute(){
  vector<int> goal;
  rep(i,W) if( arr[i] == 0 ) goal.push_back(i);
  if( goal.empty() ) { puts("0"); return; }
  vector<int> init(W);
  rep(i,W) {
    if( arr[i] >= 0 ) init[i] = MINI_IINF;
    else              init[i] = -arr[i] - i;
  }
  MixSegmentTree segtree;
  segtree.init(init.size());
  segtree.build(init);

  int index = 1;
  int left = -1, right = goal[0];
  int answer = 0;
  rep(cur,W) {
    /*
    cout << cur << " [" << arr[cur] << "] == " << answer << endl;
    cout << "<" << left << "," << right << ">" << endl;
    rep(i,W) {
      cout << get<1>(segtree.query(i,i+1)) << " ";
    } puts("");
    */
    int remain = arr[cur];

    if( arr[cur] > 0 ) {
      int maxi = 0;
      if( left != -1 ) {
        int mini = get<1>(segtree.query(left,cur));
        if( mini > 0 ) maxi = max(maxi,mini);
      } 
      if( right != -1 ) {
        int mini = get<1>(segtree.query(cur+1,right));
        if( mini > 0 ) maxi = max(maxi,mini);
      }
      answer += min(maxi,arr[cur]);
    }
    segtree.update(cur+1,W,'A',+1);
    segtree.update(0,cur+1,'A',-1);
    if( cur == right ) {
      left = right;
      if( index >= goal.size() ) right = -1;
      else                       right = goal[index++];
    }
  }
  cout << answer << endl;
}

int main(){
  scanf("%d",&W);
  rep(i,W) scanf("%d",arr+i);
  compute();
  return 0;
}

Measured memory_bytes: 10044