Two pirates Polycarpus and Vasily play a very interesting game. They have n chests with coins, the chests are numbered with integers from 1 to n. Chest number i has ai coins. 

Polycarpus and Vasily move in turns. Polycarpus moves first. During a move a player is allowed to choose a positive integer x (2·x + 1 ≤ n) and take a coin from each chest with numbers x, 2·x, 2·x + 1. It may turn out that some chest has no coins, in this case the player doesn't take a coin from this chest. The game finishes when all chests get emptied.

Polycarpus isn't a greedy scrooge. Polycarpys is a lazy slob. So he wonders in what minimum number of moves the game can finish. Help Polycarpus, determine the minimum number of moves in which the game can finish. Note that Polycarpus counts not only his moves, he also counts Vasily's moves.

Input

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of chests with coins. The second line contains a sequence of space-separated integers: a1, a2, ..., an (1 ≤ ai ≤ 1000), where ai is the number of coins in the chest number i at the beginning of the game.

Output

Print a single integer — the minimum number of moves needed to finish the game. If no sequence of turns leads to finishing the game, print -1.

Examples

Input

1
1


Output

-1


Input

3
1 2 3


Output

3

Note

In the first test case there isn't a single move that can be made. That's why the players won't be able to empty the chests.

In the second sample there is only one possible move x = 1. This move should be repeated at least 3 times to empty the third chest.
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.*;
import java.util.*;
import java.util.LinkedList;
import java.math.*;
import java.lang.*;
import java.util.PriorityQueue;
import static java.lang.Math.*;
@SuppressWarnings("unchecked")
public class Solution implements Runnable {
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars==-1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                }
                catch (IOException e) {
                    throw new InputMismatchException();
                }

                if(numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() {
            int c = read();

            while(isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if(c<'0'||c>'9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
                return res * sgn;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
    public static long min(long a,long b)
    {
        if(a>b)
        {
            return b;
        }
        return a;
    }
    public static int min(int a,int b)
    {
        if(a>b)
        {
            return b;
        }
        return a;
    }
    public static long max(long a,long b)
    {
        if(a>b)
        {
            return a;
        }
        return b;
    }
    public static int max(int a,int b)
    {
        if(a>b)
        {
            return a;
        }
        return b;
    }
    static class pair implements Comparable<pair>
    {
      int x;
      int y;
      pair(int x,int y)
      {
        this.x = x;
        this.y = y;
      }
      public int compareTo(pair b)
      {
        if(this.x>b.x)
        {
          return 1;
        }
        else if(this.x<b.x)
        {
          return -1;
        }
        else
        {
          return this.y-b.y;
        }
      }
    }
    public static int gcd(int a,int b)
    {
        if(a==0)
        return b;
        if(b==0)
        return a;
        while((a%=b)!=0&&(b%=a)!=0);
        return a^b;
    }
    public static long mod(long a)
    {
      if(a>0)
        return a;
      return -a;
    }
    static final int mod = (int)1e9+7;;
    public static long expo(long exp,long pow)
    {
      long ans = 1;
      while(pow!=0)
      {
        if((pow&1)==1)
        {
          ans = (ans*exp)%mod;
        }
        exp = (exp*exp)%mod;
        pow = pow>>1;
      }
      return ans;
    }
    static long start = 0;
    public static void start()
    {
      start = System.currentTimeMillis();
    }
    public static void end()
    {
      System.out.println(System.currentTimeMillis()-start);
    }
    public static int random(int min,int max)
    {
      return (int)((max-min)*Math.random());
    }
    public static String randString(int len)
    {
      String s = "";
      while(len-->0)
      {
          char c = (char)(97+random(0,26));
          s+=c;
      }
      return s;
    }
    public static int getmin(int[] a,int n)
    {
      int ans = 0;
      for(int i=n;i>3;i-=2)
      {
        ans+=max(a[i],a[i-1]);
        a[(i-1)/2] = max(0,a[(i-1)/2]-max(a[i],a[i-1]));
        a[i] = a[i-1] = 0;
      }
      ans+=max(a[1],max(a[2],a[3]));
      a[1] = a[2] = a[3] = 0;
      return ans;
    }
    public static void main(String args[]) throws Exception {
        new Thread(null, new Solution(),"Main",1<<26).start();
    }
    public void run() {
      InputReader sc  = new InputReader(System.in);
      PrintWriter out = new PrintWriter(System.out);
      int t1 = 1;
      //start();
      while(t1-->0)
      {
        int n  = sc.nextInt();
        int[] a = new int[n+1];
        for(int i=1;i<=n;i++)
        {
          a[i] = sc.nextInt();
        }
        if(n==1)
        {
          if(a[n]==0)
          {
            out.println(0);
          }
          else
          {
            out.println(-1);
          }
        }
        else if(n==2)
        {
          if(a[n]==0&&a[n-1]==0)
          {
            out.println(0);
          }
          else
          {
            out.println(-1);
          }
        }
        else if(n%2==0)
        {
          if(a[n]!=0)
          {
            out.println(-1);
          }
          else
          {
            out.println(getmin(a,n-1));
          }
        }
        else
        {
            out.println(getmin(a,n));
        }
      }
      //end();
      out.close();
     }
}
