1675：圆环独立集
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：3
解决：2
题目描述
给定一个长度为 $n$ 的环状数列 $a_1,a_2,...,a_n$，请从这些数字中间挑选出一个独立集，使得独立集中的数字之和达到最大。
所谓环状，是指在考虑相邻关系时，需要把 $a_1$ 和 $a_n$ 也看做是一对邻居。所谓独立集，就是挑选出的数字在原来的圆环上不能相邻。
输入
第一行：单个整数表示 $n(1\le n\le 5\times 10^5)$
第二行：$n$ 个整数表示 $a_1,a_2,...a_n(1\le a_i\le 10^6)$
第二行：$n$ 个整数表示 $a_1,a_2,...a_n(1\le a_i\le 10^6)$
输出
单个整数：表示独立的数字之和的最大值。
样例输入-1 复制
6
100 1 1 100 1 1样例输出-1 复制
200