题目描述

一个圆环上顺时针排列着 $n$ 个整数 $a_1, a_2, \ldots, a_n$，其中 $n$ 为奇数。也就是说，$a_1$ 和 $a_2$ 相邻，$a_2$ 和 $a_3$ 相邻，……，$a_{n-1}$ 和 $a_n$ 相邻，$a_n$ 和 $a_1$ 相邻。你需要对圆环上的这些数字进行若干次操作。每一次操作，你可以选择圆环中的一个整数，并将其数值设置为与其相邻两个整数的数值之和，然后删除掉与其相邻的这两个整数。这样经过若干轮操作之后，圆环上将只剩下一个整数，求这个整数的最大可能数值。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$ 且 $n$ 为奇数），表示初始时圆环上包含的整数个数。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n(0 \le a_i \le 10^9)$，两两之间以一个空格分隔，依次表示初始时圆环上的每个整数。

输出格式

输出一个整数，表示最终圆环上值剩下一个整数时，该整数可能的最大值。

样例

3
7 10 2

17

1
5

5

数据范围

• 对于 $10\%$ 的数据，$n \le 10$；
• 对于 $20\%$ 的数据，$n \le 1000$；
• 对于 $40\%$ 的数据，$n \le 10000$；
• 对于 $100\%$ 的数据，$1 \le n \le 2 \cdot 10^5, 0 \le a_i \le 10^9$。