当地的数学狂人丹尼 (Danny) 对 Omkar 最新创作的圆圈着迷。帮他解决这个圈子问题吧!
给定您 $$$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$$$ 也被认为是相邻的。在一项操作中,您在圆上选择一个数字,将其替换为与其相邻的两个元素的总和,然后从圆中删除两个相邻元素。如此重复,直到圆圈中只剩下一个数字,我们称之为循环值。
帮助 Danny 在一系列操作后找到最大可能的循环值。
输入
第一行包含一个奇数整数 $$$n$$$ ($$$1 \leq n < 2 \cdot 10^5$$$, $$$n$$$ 是奇数) — 圆的初始大小。
第二行包含 $$$n$$$ 整数 $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$0 \leq a_{i} \leq 10^9$$$) — 圆圈中的初始数字。
输出
对给定圆应用一些操作序列后输出最大可能的圆值。
示例
输入 #1
3 7 10 2
输出 #1
17
输入 #2
1 4
输出 #2
4
注意
对于第一个测试用例,以下是如何获取 $$$17$$$ 的循环值:
选择索引 $$$3$$$ 处的数字。相邻元素的总和等于$$$17$$$。从圆圈中删除 $$$7$$$ 和 $$$10$$$,并将 $$$2$$$ 替换为 $$$17$$$。
请注意,答案可能不适合 $$$32$$$ 位整数。