На столе в ряд лежат n кучек камней. В i-й кучке находится a_i камней.

Два игрока ходят по очереди, первым ходит игрок №1. За один ход игрок может взять с левого конца ряда либо одну кучку, либо две подряд идущие кучки. Все камни из взятых кучек переходят этому игроку.

Игра продолжается, пока кучки не закончатся. Оба игрока действуют оптимально и стремятся набрать как можно больше камней.

Требуется определить, сколько камней в итоге получит игрок №1.

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

Первая строка содержит одно целое число n — количество кучек.

Вторая строка содержит n целых чисел a_i — количество камней в кучках.

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

Выведите одно целое число — количество камней, которое наберёт игрок №1 при оптимальной игре.

Ограничения

• 1 <= n <= 100000
• 1 <= a_i <= 10000

Ответ может не помещаться в 32-битный целочисленный тип.

Примеры

Пример 1

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

1
1

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

1

Пример 2

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

2
10000 1

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

10001