Алгоритмы и структуры данных

Имя входного файла: input.txt 

Имя выходного файла: output.txt 

Ограничение по времени: 1 с 

Ограничение по памяти: 64 МБ

В одном очень длинном и узком пруду по кувшинкам прыгает лягушка. Кувшинки в пруду расположены в один ряд. Лягушка начинает прыгать с первой кувшинки ряда и хочет закончить на последней. Но в силу вредности характера лягушка согласна прыгать только вперед через одну или через две кувшинки. Например, с кувшинки номер 1 она может прыгнуть лишь на кувшинки номер 3 и номер 4. 

На некоторых кувшинках сидят комарики. А именно, на i-й кувшинке сидят ai комаров. Когда лягушка приземляется на кувшинку, она съедает всех комариков, сидящих на ней. Лягушка хочет спланировать свой маршрут так, чтобы съесть как можно больше комаров. Помогите ей: подскажите, какое максимальное число комаров она может съесть за своё путешествие. 

Формат входных данных 

Первая строка входа содержит число n кувшинок в пруду (1 ≤ n ≤ 1000). Вторая строка содержит n чисел, разделённых одиночными пробелами: i-е число сообщает, сколько комаров сидит на i-й кувшинке. Все числа целые, неотрицательные и не превосходят 1000. 

Формат выходных данных 

Выведите максимальное число комаров, которое может съесть лягушка. Если лягушка не может добраться до последней кувшинки, то выведите −1.

Пример.

input.txt

6

1 100 3 4 1000 0

2

8 9

output.txt

5

-1