C. Игра с монетами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Два пирата Поликарп и Василий играют в очень интересную игру. У них есть n сундуков с монетами, сундуки пронумерованы целыми числами от 1 до n. В сундуке c номером i находится ai монеток.

Поликарп и Василий по очереди совершают ходы. Первым ходит Поликарп. За один ход игроку разрешается выбрать целое положительное число x (2·x + 1 ≤ n) и взять по монетке из трех сундуков с номерами x, 2·x, 2·x + 1. Может оказаться, что в каком-то из этих сундуков нет монеток, в таком случае игрок не берет монетку из этого сундука. Игра заканчивается, когда все сундуки становятся пустыми.

Поликарп — человек не алчный. Поликарп — человек ленивый. Поэтому ему очень интересно, за какое наименьшее количество ходов может закончиться игра. Помогите Поликарпу, определите за какое минимальное количество ходов может закончиться игра. Учтите, Поликарп считает не только свои ходы, ходы Василия он тоже считает.

Входные данные

В первой строке записано единственное целое число n (1 ≤ n ≤ 100) — количество сундуков с монетами. Во второй строке записана последовательность целых чисел, разделенных пробелами: a1, a2, ..., an (1 ≤ ai ≤ 1000), где ai — количество монет в сундуке с номером i на начало игры.

Выходные данные

Выведите единственное целое число — за какое наименьшее количество ходов может закончиться игра. Если ни при какой последовательности ходов игра не заканчивается выведите -1.

Примеры
Входные данные
1
1
Выходные данные
-1
Входные данные
3
1 2 3
Выходные данные
3
Примечание

В первом тестовом примере не существует ни одного хода, который можно было бы сделать. Поэтому опустошить сундуки не получится.

Во втором тестовом примере существует только один возможный ход x = 1. Этот ход нужно повторить как минимум 3 раза, чтобы опустошить третий сундук.