← 返回题目列表

Codeforces · 1372/D

D. 奥姆卡和圆圈

中文机器翻译题面 查看原题

当地的数学狂人丹尼 (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$$$ 位整数。