Omkar 与圆环

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，它们按顺时针顺序排成一个圆环，其中 $n$ 为奇数。相邻下标的元素相邻，$a_n$ 与 $a_1$ 也相邻。

每次操作可以选择圆环上的一个数，把它替换为它的两个相邻元素之和，然后删除这两个相邻元素。重复操作直到圆环上只剩一个数，这个数称为圆环值。

求圆环值的最大可能值。

输入格式

第一行包含一个奇数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出圆环值的最大可能值。

样例输入 1

3
7 10 2

样例输出 1

17

样例输入 2

1
4

样例输出 2

4

数据范围

对于所有数据，$1\le n<2\times10^5$，$n$ 为奇数，$0\le a_i\le10^9$。