Omkar and Circle

题意翻译

题意： 给出 $n$ 个非负整数 $a_1,a_2,\cdots , a_n$ 排成一个圆圈，$n$ 一定是个奇数。 对于所有的 $2\le i \le n$ ，$a_{i-1}$ 与 $a_i$ 被认为是相邻的，$a_1$ 和 $a_n$ 也被认为是相邻的。 你有一种操作：在圆圈上选一个元素，将其**替换**为相邻两个元素的和，然后从圆圈中删除两个相邻的元素。重复这个操作直到圆圈中仅剩一个数字为止，我们称其为圈圈值。 问能达到的最大圈圈值为多少。 输入： 第一行包含一个**奇数**整数 $n$ $(1\le n \le 2\times 10^5)$ - 圆圈内初始的元素个数。 第二行包含 $n$ 个整数 $a_1 , a_2 , \cdots a_n$ $(0\le a_i \le 10^9)$ 输出： 输出能达到的最大圈圈值。 样例解释： 对于第一个样例，这是获得17的圈圈值的方法： 对 $a_3$ 进行操作。相邻元素的总和等于17。从圆中删除7和10，然后将2替换为17。 请注意，答案可能不适合32位整数。 translated by MicroMaker

题目描述

Danny, the local Math Maniac, is fascinated by circles, Omkar's most recent creation. Help him solve this circle problem! You are given $ n $ nonnegative integers $ a_1, a_2, \dots, a_n $ arranged in a circle, where $ n $ must be odd (ie. $ n-1 $ is divisible by $ 2 $ ). Formally, for all $ i $ such that $ 2 \leq i \leq n $ , the elements $ a_{i - 1} $ and $ a_i $ are considered to be adjacent, and $ a_n $ and $ a_1 $ are also considered to be adjacent. In one operation, you pick a number on the circle, replace it with the sum of the two elements adjacent to it, and then delete the two adjacent elements from the circle. This is repeated until only one number remains in the circle, which we call the circular value. Help Danny find the maximum possible circular value after some sequences of operations.

输入输出格式

输入格式

The first line contains one odd integer $ n $ ( $ 1 \leq n < 2 \cdot 10^5 $ , $ n $ is odd) — the initial size of the circle. The second line contains $ n $ integers $ a_{1},a_{2},\dots,a_{n} $ ( $ 0 \leq a_{i} \leq 10^9 $ ) — the initial numbers in the circle.

输出格式

Output the maximum possible circular value after applying some sequence of operations to the given circle.

输入输出样例

输入样例 #1

3
7 10 2

输出样例 #1

17

输入样例 #2

1
4

输出样例 #2

4

说明

For the first test case, here's how a circular value of $ 17 $ is obtained: Pick the number at index $ 3 $ . The sum of adjacent elements equals $ 17 $ . Delete $ 7 $ and $ 10 $ from the circle and replace $ 2 $ with $ 17 $ . Note that the answer may not fit in a $ 32 $ -bit integer.