题目描述
给定一个长度为 $n$ 的环状数列 $a_1,a_2,\cdots, a_n$，请从这些数字中间挑选出一个独立集，使得独立集中的数字之和达到最大。
所谓环状，是指在考虑相邻关系时，需要把 $a_1$ 和 $a_n$ 也看做是一对邻居。所谓独立集，就是挑选出的数字在原来的圆环上不能相邻。
输入
第一行：单个整数表示 $n$。
第二行：$n$ 个整数表示 $a_1, a_2, \cdots, a_n$。
输出
单个整数：表示独立的数字之和的最大值。
样例输入输出
输入#2
复制
6
100 1 1 100 1 1
提示
+ 对于 $30\%$ 的数据，$1\leq n\leq 20$；
+ 对于 $60\%$ 的数据，$1\leq n\leq 5000$；
+ 对于 $100\%$ 的数据，$1\leq n\leq 500,000$，
+ $1\leq a_i\leq 1,000,000$。
样例2说明:这个例子告诉我们最优独立集不一定是最大独立集