G. 圆环独立集

传统题

文件IO：set

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 n 的环状数列 a1,a2,⋯,an ，请从中间挑选出一些数字组成一个独立集，使得该独立集中的数字之和达到最大。

所谓环状，是指在考虑相邻关系时，需要把 a1 和 an 也看做是一对邻居。所谓独立集，就是挑选出的数字在原来的圆环上不能相邻。

第一行：单个整数表示 n。

第二行：n 个整数表示a1,a2,⋯,an。

单个整数：表示独立集的数字之和的最大值。

5
1 1 1 1 1

6
100 1 1 100 1 1

对于 30% 的数据，1≤n≤20；

对于 60% 的数据，1≤n≤5000；

对于 100% 的数据，1≤n≤500,000

1≤ai≤1,000,000。