/*
--- Charakterystyka klasy AVL ---
Implementacja drzewa AVL, bez rekurencji
z nastepujacymi operacjami:
- insertUnique()    O(log n)

Do porownywania elementów uzywany jest operator "<" i "=="

*/

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include <time.h>

#define FOR(x, b, e) for(long x = b; x <= (e); x++)
#define VAR(v, n) __typeof(n) v = (n)
#define ALL(c) (c).begin(), (c).end()
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define DEBUG if (debug)
#define MIN(a,b) ((a>b)?b:a)
#define MAX(a,b) ((a>b)?a:b)
#define LL long long

using namespace std;

bool OK;

class Error {
   public:
   string description;
   Error(string p_description) { description=p_description; };
};

LL delta_zakres, delta_value;
LL INF=1000000000;
LL SMALLER_INF=100000000;

class Zakres
{
    public:
    LL pocz, kon;
    LL value;
    LL getPocz() { return pocz+delta_zakres; };
    LL getKon() { return kon+delta_zakres; };
    LL getValue() { return value+delta_value; };
    Zakres() { pocz=0; kon=0; value=0; };
    Zakres(const Zakres& another) { pocz=another.pocz; kon=another.kon; value=another.value; };
    Zakres(LL p_pocz, LL p_kon, LL p_value) { pocz=p_pocz; kon=p_kon; value=p_value; };
    inline bool operator < (const Zakres& another) { return (pocz<another.pocz); };
    inline bool operator >= (const Zakres& another) { return (pocz>=another.pocz); };
    inline bool operator <= (const Zakres& another) { return (pocz<=another.pocz); };
    inline bool operator == (const Zakres& another) { return (pocz==another.pocz); };
    void showInfo()
    {
        cout << pocz+delta_zakres << ".." << kon+delta_zakres << ": " << value+delta_value << "\n";
    }
};


template <class AvlElem>
class AvlTreeNode
// Class representing a node in an AVL Tree
{
   public:
   AvlElem value;
   LL count, count2;
   long o;
   short w;
   AvlTreeNode *left;
   AvlTreeNode *right;

   //constructor
   AvlTreeNode(AvlElem pValue)
   {
      value=pValue; this->count=1; o=0;
      w=0; left=NULL; right=NULL;
   };

   pair<LL,LL> calculate(LL k, LL ileTrzeba, long obliczenie)
   {
       //cout << "calculating in node " << value << " (" << count << ") k=" << k << " ileTrzeba=" << ileTrzeba << "\n";
       if (value>=k)
       {
           if (left==NULL) return pair<LL,LL>(0,0);
           else return left->calculate(k, ileTrzeba, obliczenie);
       }
       else
       {
           // moje value jest < k, zatem jest potencjalnym kandydatem
            if (o==obliczenie)
            {
                // juz tu bylem w ramach tego obliczenia, uzywam count2
            }
            else
            {
                // pierwszy raz w tym wezle w ramach tego obliczenia:
                count2=count; o=obliczenie;
            }
           pair<LL,LL> w(0,0);
           if (right!=NULL) w=right->calculate(k,ileTrzeba, obliczenie);
           if (w.second>=ileTrzeba) return w; // juz jest OK
           ileTrzeba-=w.second;
           LL allHere=count2*value;
           if (allHere>=ileTrzeba)
           {
               // wystarczy to, co jest tutaj
               LL i=ileTrzeba/value;
               w.first+=i; ileTrzeba-=i*value; w.second+=i*value; count2-=i;
               if (ileTrzeba>0) { w.first++; w.second+=value; count2--; }
               //cout << " zwracam " << w.first << " " << w.second << "\n";
               return w;
           }
           else
           {
               // biore wszystko i ide dalej
               w.first+=count2; w.second+=allHere; ileTrzeba-=allHere;
               if (left!=NULL)
               {
                   pair<LL,LL> wL = left->calculate(k, ileTrzeba, obliczenie);
                   w.first+=wL.first; w.second+=wL.second;
               }
               //cout << " zwracam " << w.first << " " << w.second << "\n";
               return w;
           }
       }
   }

   void display(long level)
   // Displays self.
   {
      for (long i=0; i<level; i++) cout << "  ";
      cout << value << " (" << w << ")  count=" << count << "\n";
      if ((left==NULL)&&(right==NULL)) return;
      if (left==NULL) { for (long i=0; i<level+1; i++) cout << "  "; cout << "left NULL\n"; }
      else left->display(level+1);
      if (right==NULL) { for (long i=0; i<level+1; i++) cout << "  "; cout << "right NULL\n"; }
      else right->display(level+1);
   };

   void displayValues()
   // Displays self.
   {
       if (left!=NULL) left->displayValues();
       value.showInfo();
       if (right!=NULL) right->displayValues();
   };


   void checkBST(long a, long b)
   {
     if ((value<a)||(value>b)) {
        cout << "Error BST in node " << value << "\n";
        cout.flush();
        throw new Error("");
     };
     if (left!=NULL) left->checkBST(a, value-1);
     if (right!=NULL) right->checkBST(value+1, b);
   };

   long checkAVL()
   // returns height of the tree
   {
      long leftHeight=0;
      long rightHeight=0;
      if (left!=NULL) leftHeight=left->checkAVL();
      if (right!=NULL) rightHeight=right->checkAVL();
      long height=1 + MAX(leftHeight, rightHeight);
      long delta = rightHeight-leftHeight;
      if ((delta<-1)||(delta>+1)) throw Error("07");
      if (delta!=w) {
        cout << "Node: " << value << " right: " << rightHeight << " left: " << leftHeight << " w=" << w << "\n";
        throw Error("08");
      };
      return height;
   };

   long treeSize()
   {
       if (this->count<=0) OK=false;
       long s=this->count;
       if (left!=NULL) s+=left->treeSize();
       if (right!=NULL) s+=right->treeSize();
       return s;
   }

   AvlTreeNode<AvlElem>* rotateSingleToTheRight()
   {
      AvlTreeNode<AvlElem> *p=this;
      AvlTreeNode<AvlElem> *q=p->left;
      p->left=q->right;
      q->right=p;
      p->w=0; q->w=0;
      return q;
   };

   AvlTreeNode<AvlElem>* rotateSingleToTheLeft()
   {
      AvlTreeNode<AvlElem> *p=this;
      AvlTreeNode<AvlElem> *q=p->right;
      p->right=q->left;
      q->left=p;
      p->w=0; q->w=0;
      return q;
   };

   AvlTreeNode<AvlElem>* rotateGammaSingleToTheRight()
   {
      AvlTreeNode<AvlElem> *p=this;
      AvlTreeNode<AvlElem> *q=p->left;
      p->left=q->right;
      q->right=p;
      p->w=-1; q->w=1;
      return q;
   };

   AvlTreeNode<AvlElem>* rotateGammaSingleToTheLeft()
   {
      AvlTreeNode<AvlElem> *p=this;
      AvlTreeNode<AvlElem> *q=p->right;
      p->right=q->left;
      q->left=p;
      p->w=1; q->w=-1;
      return q;
   };

   AvlTreeNode<AvlElem>* rotateDoubleToTheRight()
   {
      AvlTreeNode<AvlElem> *p=this;
      AvlTreeNode<AvlElem> *q=p->left;
      AvlTreeNode<AvlElem> *r=q->right;
      p->left=r->right;
      q->right=r->left;
      r->right=p; r->left=q;
      if (r->w==0) { p->w=0; q->w=0; }
      else if (r->w==-1) { p->w=1; q->w=0; }
      else if (r->w==+1) { p->w=0; q->w=-1; }
      else throw new Error("12");
      r->w=0;
      return r;
   };

   AvlTreeNode<AvlElem>* rotateDoubleToTheLeft()
   {
      AvlTreeNode<AvlElem> *p=this;
      AvlTreeNode<AvlElem> *q=p->right;
      AvlTreeNode<AvlElem> *r=q->left;
      p->right=r->left;
      q->left=r->right;
      r->left=p; r->right=q;
      if (r->w==0) { p->w=0; q->w=0; }
      else if (r->w==-1) { p->w=0; q->w=1; }
      else if (r->w==+1) { p->w=-1; q->w=0; }
      else throw new Error("11");
      r->w=0;
      return r;
   };

};

template <class AvlElem>
class AvlTree
// class representing AVL Tree
{
   AvlTreeNode<AvlElem> *root;
   stack<AvlTreeNode<AvlElem>* > trace;
   public:
   AvlTree() { root=NULL; };

   bool isEmpty()
   {
       return (root==NULL);
   }

   void displayValues()
   {
        if (root==NULL) cout << "Empty tree\n";
        else root->displayValues();
   }

   void insertValue(AvlElem pValue)
   //Inserts pValue into the tree.
   //Returns true if the value was already in the tree
   {
      bool found = findValue(pValue);
      if (found)
      {
        trace.top()->count++;
        return;
      }
      AvlTreeNode<AvlElem> *newNode = new AvlTreeNode<AvlElem>(pValue);
      if (root==NULL) root=newNode;
      else {
         if (trace.empty()) throw new Error("13");
         AvlTreeNode<AvlElem> *parent = trace.top();
         if (pValue < parent->value) { parent->left=newNode; fixAfterInsert(newNode); }
         else { parent->right=newNode; fixAfterInsert(newNode); }
      };
   };

   bool deleteValue(AvlElem pValue)
   // Removes given value from the tree.
   // Returns true if the value was in the tree.
   {
      // cout << "Deleting " << pValue << "\n";
      bool found = findValue(pValue);
      if (!found) return false;
      AvlTreeNode<AvlElem> *node=trace.top();
      //cout << "Found: " << node->value << " count=" << node->count << "\n";
      trace.top()->count--;
      //cout << "And now: " << node->value << " count=" << node->count << "\n";
      if ((trace.top()->count)==0) reallyDeleteNode();
      return true;
   };

   pair<LL,LL> calculate(LL k, LL ileTrzeba, long obliczenie)
   {
       if (root==NULL) return pair<LL,LL>(0,0);
       return root->calculate(k, ileTrzeba, obliczenie);
   }

   AvlElem deleteSmallestValue()
   // Removes smallest node and returns its value.
   // If tree is empty, raises an Error
   {
      if (root==NULL) throw new Error("Tree is empty!");
      ensureTraceEmpty();
      AvlTreeNode<AvlElem> *current=root; trace.push(current);
      while (current->left!=NULL) {
         current=current->left; trace.push(current);
      };
      AvlElem value = current->value;
      current->count--;
      if (current->count==0) reallyDeleteNode();
      return value;
   };

   AvlElem deleteGreatestValue()
   // Removes smallest node and returns its value.
   // If tree is empty, raises an Error
   {
      if (root==NULL) throw new Error("Tree is empty!");
      ensureTraceEmpty();
      AvlTreeNode<AvlElem> *current=root; trace.push(current);
      while (current->right!=NULL) {
         current=current->right; trace.push(current);
      };
      AvlElem value = current->value;
      current->count--;
      if (current->count==0) reallyDeleteNode();
      return value;
   };

   bool doesContain(AvlElem pValue)
   //Returns true if the value is in the tree.
   {
      AvlTreeNode<AvlElem> *current=root;
      while (current!=NULL) {
         if (current->value==pValue) return true;
         if (pValue<current->value) current=current->left; else current=current->right;
      };
      return false;
   };

   AvlTreeNode<AvlElem>* smallestNode()
   // Returns smallest node in the tree
   {
      if (root==NULL) return NULL;
      AvlTreeNode<AvlElem> *current=root;
      while (current->left!=NULL) current=current->left;
      return current;
   };

   AvlTreeNode<AvlElem>* greatestNode()
   // Returns greatest node in the tree
   {
      if (root==NULL) return NULL;
      AvlTreeNode<AvlElem> *current=root;
      while (current->right!=NULL) current=current->right;
      return current;
   };

   AvlTreeNode<AvlElem>* smallestGreaterThanNode(AvlElem &pValue)
   // Returns node, which is smallest between greater than pValue
   {
      AvlTreeNode<AvlElem> *current=root;
      AvlTreeNode<AvlElem> *candidate=NULL;
      while (current!=NULL) {
         if (current->value>pValue) {
            candidate=current;
            current=current->left;
         } else current=current->right;
      };
      return candidate;
   };
   AvlTreeNode<AvlElem>* smallestGreaterOrEqualThanNode(AvlElem &pValue)
   // Returns node, which is smallest between greater or equal than pValue
   {
      AvlTreeNode<AvlElem> *current=root;
      AvlTreeNode<AvlElem> *candidate=NULL;
      while (current!=NULL) {
         if (current->value>=pValue) {
            candidate=current;
            current=current->left;
         } else current=current->right;
      };
      return candidate;
   };
   AvlTreeNode<AvlElem>* greatestSmallerThanNode(AvlElem &pValue)
   // Returns node, which is greatest between smaller than pValue
   {
      AvlTreeNode<AvlElem> *current=root;
      AvlTreeNode<AvlElem> *candidate=NULL;
      while (current!=NULL) {
         if (current->value<pValue) {
            candidate=current;
            current=current->right;
         } else current=current->left;
      };
      return candidate;
   };
   AvlTreeNode<AvlElem>* greatestSmallerOrEqualThanNode(AvlElem &pValue)
   // Returns node, which is greatest between smaller or equal than pValue
   {
      AvlTreeNode<AvlElem> *current=root;
      AvlTreeNode<AvlElem> *candidate=NULL;
      while (current!=NULL) {
         if (current->value<=pValue) {
            candidate=current;
            current=current->right;
         } else current=current->left;
      };
      return candidate;
   };


   void display()
   {
        if (root==NULL) cout << "Empty tree\n";
        else root->display(0);
   };

   void check()
   {
      if (root==NULL) return; // tree is correct
      root->checkBST(-1000000000, 1000000000);
      root->checkAVL();
   };

   long treeSize()
   {
       if (root==NULL) return 0;
       return root->treeSize();
   }

   private:

   void ensureTraceEmpty()
   // Ensures that stack "trace" is empty.
   {
      while (!trace.empty()) trace.pop();
   };

   bool findValue(AvlElem &pValue)
   //Finds given pValue in the tree.
   //Returns true if the value is found.
   {
      ensureTraceEmpty();
      AvlTreeNode<AvlElem> *current=root;
      while (current!=NULL) {
         trace.push(current);
         if (current->value==pValue) return true;
         if (pValue<current->value) current=current->left; else current=current->right;
      };
      return false;
   };

   void fixAfterInsert(AvlTreeNode<AvlElem> *child)
   // Fixes AVL property after insertion.
   // delta=-1 means: left tree is higher
   // delta=+1 means: right tree is higher.
   {
      AvlTreeNode<AvlElem> *current = trace.top(); trace.pop();
      long delta;
      while (current!=NULL) {
         if (current->left==child) delta=-1; else delta=+1;
         current->w += delta;
         if (current->w==0) return; // the tree does not change height
         if (current->w==delta) {
           // the tree changes height, but rotation is not required
           child=current;
           if (trace.empty()) return;
           current=trace.top(); trace.pop();
         }
         else {
            AvlTreeNode<AvlElem> *parent;
            if (trace.empty()) parent=NULL; else parent = trace.top();
            AvlTreeNode<AvlElem> *newTop;
            if (current->w==-2) {
               if (current->left->w==-1) newTop=current->rotateSingleToTheRight();
               else if (current->left->w==+1) newTop=current->rotateDoubleToTheRight();
               else throw new Error("Error 002");
            }
            else if (current->w==+2) {
               if (current->right->w==+1) newTop=current->rotateSingleToTheLeft();
               else if (current->right->w==-1) newTop=current->rotateDoubleToTheLeft();
               else throw new Error("Error 002");
            }
            else throw new Error("Error 001");
            if (parent==NULL) root=newTop;
            else {
               if (current==parent->left) parent->left=newTop; else parent->right=newTop;
            };
            return; // no further action is required.
         };
      };
   };

   void reallyDeleteNode()
   // Removes a node from the tree - node found by findValue().
   {
      if (trace.empty()) throw new Error("15");
      AvlTreeNode<AvlElem> *toDelete=trace.top();
      if ((toDelete->left!=NULL)&&(toDelete->right!=NULL)) {
        // go to the greatest value in left subtree:
        AvlTreeNode<AvlElem> *current=toDelete->left;
        trace.push(current);
        while (current->right!=NULL) { current=current->right; trace.push(current); };
        toDelete->value=current->value;
        toDelete->count=current->count;
        toDelete->count2=current->count2;
        toDelete->o=current->o;
        toDelete=current;
      };
      // now really remove "toDelete" from the tree
      // we know it has at most one child
      AvlTreeNode<AvlElem> *child=toDelete->left;
      if (child==NULL) child=toDelete->right;
      trace.pop(); // pop "toDelete" from the trace;
      AvlTreeNode<AvlElem> *parent;
      long delta;
      if (trace.empty()) {
        // "toDelete" is a root
        root=child;
        delete toDelete;
        return;
      } else {
         parent=trace.top();
         if (toDelete==parent->left) {
           parent->left=child; delta=+1;
         } else {
           parent->right=child; delta=-1;
         };
         delete toDelete;
      };
      fixAfterDeletion(delta);
   };

   void fixAfterDeletion(long delta)
   // Fixes AVL property after deletion
   {
      AvlTreeNode<AvlElem> *current=trace.top(); trace.pop();
      while (current!=NULL) {
         current->w += delta;
         if (current->w==delta) return;
         if (current->w==0) {
           // just pass it higher;
           if (trace.empty()) return;
           AvlTreeNode<AvlElem> *child=current;
           current=trace.top(); trace.pop();
           if (current->left==child) delta=+1; else delta=-1;
         } else {
            // we will have to rotate:
            bool stop=false;
            AvlTreeNode<AvlElem> *parent=NULL;
            AvlTreeNode<AvlElem> *newTop;
            if (!trace.empty()) parent=trace.top();
            if (current->w==-2) {
              // rotations to the right
               if (current->left->w==-1) newTop=current->rotateSingleToTheRight();
               else if (current->left->w==+1) newTop=current->rotateDoubleToTheRight();
               else if (current->left->w==0) {
                    newTop=current->rotateGammaSingleToTheRight();
                    stop=true;
               } else throw new Error("Error 002");
            } else if (current->w==+2) {
              // rotations to the left
               if (current->right->w==+1) newTop=current->rotateSingleToTheLeft();
               else if (current->right->w==-1) newTop=current->rotateDoubleToTheLeft();
               else if (current->right->w==0) {
                    newTop=current->rotateGammaSingleToTheLeft();
                    stop=true;
               } else throw new Error("Error 002");
            } else throw new Error("14");

            if (parent==NULL) root=newTop;
            else {
               if (current==parent->left) {
                  parent->left=newTop; delta=+1;
               } else { parent->right=newTop; delta=-1; };
            };
            if (stop) return;
            current=parent; if (!trace.empty()) trace.pop();
         };
      };
   };



};

AvlTree<Zakres> t;

void showInfo(AvlTreeNode<Zakres> *node)
{
    cout << "Info: ";
    if (node==NULL) cout << "Empty\n"; else cout << node->value.pocz << ".." << node->value.kon << ": " << node->value.value << "\n";
}

void ulepsz(LL f, LL valu)
{
    Zakres zf(f,0,0);
    AvlTreeNode<Zakres> *node = t.greatestSmallerOrEqualThanNode(zf);
    //showInfo(node);
    LL po,ko; po=f;
    if (node==NULL) {
        node = t.smallestNode();
        ko=node->value.pocz-1;
    } else {
        if (node->value.value<=valu) return; // nic interesujacego
        ko=node->value.kon;
        if (node->value.pocz!=f) {
            // kawalek zostaje:
            node->value.kon=f-1;
        } else {
            // ten node jest caly do usuniecia:
            t.deleteValue(zf);
        }
    }
    bool koniec=false;
    while (!koniec && ko<SMALLER_INF)
    {
        // szukaj wezla do usuniecia:
        zf.pocz=ko+1;
        node = t.greatestSmallerOrEqualThanNode(zf);
        if (node->value.value>=valu)
        {
            // do usuniecia
            ko=node->value.kon;
            t.deleteValue(zf);
        }
        else koniec=true; // dalej nie usuwamy
    }
    zf.pocz=po; zf.kon=ko; zf.value=valu; t.insertValue(zf);
}

int main()
{
    // magic formula, which makes streams work faster:
	ios_base::sync_with_stdio(0);
	INF=INF*INF; SMALLER_INF=SMALLER_INF*SMALLER_INF;
	delta_zakres=0; delta_value=0;
	LL pop_delta_zakres; LL pop_delta_value;

	long n; cin >> n;
	Zakres z;
	LL kp=0; LL p;

	long pos=1;
	cin >> p;
	while (p==0)
    {
        pos++;
        if (pos>n)
        {
            // same 0:
            cout << "0\n"; return 0;
        }
        cin >> p;
    }

	z.pocz=-p; z.kon=INF; z.value=0; t.insertValue(z);
	//cout << "--- After first step at: " << pos << "\n";
	//t.displayValues();
	AvlTreeNode<Zakres> *node = NULL;

	FOR(i,pos+1,n)
	{
	    kp++;
	    cin >> p;
	    if (p==0) { continue; };
	    z.pocz=0-delta_zakres;
	    node = t.greatestSmallerOrEqualThanNode(z);
	    pop_delta_zakres=delta_zakres; pop_delta_value=delta_value;
	    LL k3=0; if (node!=NULL) k3=node->value.value;
	    delta_zakres-=p; delta_value+=kp; kp=0;
	    //cout << "--- Step " << i << " before bettering:\n"; t.displayValues();
	    if (node!=NULL) {
            //cout << " ulepszanie: " << -p << " " << k3+pop_delta_value << "\n";
            ulepsz(-p-delta_zakres, k3+pop_delta_value-delta_value);
	    }
	    //cout << "--- Step " << i << " after bettering:\n"; t.displayValues();
	    //cout << "\n";
	}
	z.pocz=0-delta_zakres;
    node = t.greatestSmallerOrEqualThanNode(z);
    if (node==NULL) cout << "-1\n";
    else cout << node->value.value+delta_value << "\n";

    return 0;
};