环形祭坛

题目描述

在遗迹的中心，有一座古老的圆形祭坛。祭坛的边缘等距排列着 $n$ 座石台，按顺时针方向依次编号为 $1, 2, \dots, n$。由于祭坛是圆形的，石台 $n$ 与石台 $1$ 也是相邻的。

每座石台上都放置着一块蕴含能量的灵石，第 $i$ 座石台上的灵石能量值为 $a_i$。

你需要从中挑选一些灵石来激活祭坛。然而，石台之间存在强烈的能量干扰：不能同时激活三座及三座以上连续相邻的石台。

例如，如果 $n=5$，激活石台 $\{1, 2, 4\}$ 是可以的，但激活 $\{1, 2, 3\}$ 或 $\{5, 1, 2\}$ 都会因为违反禁制而导致激活失败。

请问在不违反禁制的前提下，你最多能激活的灵石能量总和是多少？

输入格式

第一行包含一个整数 $n$，表示石台的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每座石台上的灵石能量值。

输出格式

输出一个整数，表示能够激活的最大能量总和。

输入输出样例 #1

输入 #1

5
10 20 30 40 50

输出 #1

120

样例 1 说明

最优方案是激活 $\{2, 3, 5\}$ 或 $\{1, 3, 4\}$ 等，使得不存在 3 个连续激活。 例如激活 $\{2, 3, 4, 5\}$ 就不行，因为 2,3,4 连续。 例如激活 $\{5, 1, 2\}$ 也不行，因为祭坛是圆形的，5,1,2 也是连续的。 在 $n=5$ 且所有能量相同为 10 时，最多选 3 个，总和 30。本例中通过避开 $\{1, 4\}$ 或其他组合获得最大值 120。

输入输出样例 #2

输入 #2

6
10 10 10 10 10 10

输出 #2

40

数据范围

对于 $60\%$ 的数据，$3 \le n \le 1000$。

对于 $100\%$ 的数据，$3 \le n \le 10^5$，$0 \le a_i \le 10^9$。