Задача P. Лестница

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

У лестницы n ступенек, пронумерованных числами 1, 2, ... , n снизу вверх. На каждой ступеньке написано число. Начиная с подножия лестницы (его можно считать ступенькой с номером 0), требуется взобраться на самый верх (ступеньку с номером n). За один шаг можно подниматься на одну или на две ступеньки. После подъёма числа, записанные на посещённых ступеньках, складываются. Нужно подняться по лестнице так, чтобы сумма этих чисел была как можно больше.

Формат входного файла

В первой строке входного файла записано целое число n (1 ⩽ n ⩽ 100). Во второй строке заданы целые числа a1, a2, ... , an через пробел ( − 10 000 ⩽ ai ⩽ 10 000) "--- это числа, записанные на ступеньках.

Формат выходного файла

В первой строке выходного файла выведите одно число "--- максимальную сумму, которую можно получить, поднявшись по данной лестнице.

Ограничения

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
3
2
2
2 -1
1
3
3
-1 2 1
3

0.115s 0.017s 15