CF1372D Omkar and Circle

Danny 是当地的数学狂人，他对 Omkar 最近创造的圆圈非常着迷。请帮助他解决这个关于圆圈的问题！ 给定 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，它们按顺时针顺序排列成一个圆圈，其中 $n$ 必须是奇数（即 $n-1$ 能被 $2$ 整除）。形式化地说，对于所有满足 $2 \leq i \leq n$ 的 $i$，元素 $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$），表示圆圈中的初始数字。

输出经过若干次操作后，圆圈值的最大可能值。

对于第一个测试用例，可以这样得到圆圈值 $17$： 选择下标为 $3$ 的数字，其相邻元素之和为 $17$。将 $7$ 和 $10$ 从圆圈中删除，并用 $17$ 替换 $2$。 注意，答案可能无法用 $32$ 位整数表示。 由 ChatGPT 4.1 翻译