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

Дэнни, местный математик-маньяк, очарован кругами, самым последним творением Омкара. Помогите ему решить эту задачу о круге!

Вам даны $$$n$$$ неотрицательных целых чисел $$$a_1, a_2, \dots, a_n$$$, расположенных по кругу, где $$$n$$$ гарантированно будет нечетным (т.е. $$$n-1$$$ делится на $$$2$$$). Формально для всех $$$i$$$ таких, что $$$2 \leq i \leq n$$$, элементы $$$a_{i - 1}$$$ и $$$a_i$$$ считаются соседними, а $$$a_n$$$ и $$$a_1$$$ также рассматриваются как соседние. За одну операцию вы выбираете число в круге, заменяете его суммой двух соседних элементов, а затем удаляете два соседних элемента из круга. Это повторяется до тех пор, пока в круге не останется только одно число, которое мы называем круговым значением.

Помогите Дэнни найти максимально возможное круговое значение после некоторой последовательности операций.

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

Первая строка содержит одно нечетное целое число $$$n$$$ ($$$1 \leq n < 2 \cdot 10^5$$$, $$$n$$$ нечетно)  — начальный размер круга.

Вторая строка содержит $$$n$$$ целых чисел $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$0 \leq a_{i} \leq 10^9$$$)  — начальные числа в круге.

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

Выведите максимально возможное круговое значение после применения некоторой последовательности операций к данному кругу.

Примеры
Входные данные
3
7 10 2
Выходные данные
17
Входные данные
1
4
Выходные данные
4
Примечание

Для первого примера круговое значение $$$17$$$ получается так:

Выберите число с индексом $$$3$$$. Сумма соседних элементов равна $$$17$$$. Удалите $$$7$$$ и $$$10$$$ из круга и замените $$$2$$$ на $$$17$$$.

Обратите внимание, что ответ может выйти за пределы $$$32$$$-разрядного целого числа.