T321589 环上最大独立集

给出一个有 $n$ 个点的环，每个点有点权 $a_i$，求满足点集内任何两个点在环上不相邻，且点权和最大的点集的点权和。 注意点 $1$ 和 点 $n$ 是相邻的。

第一行输入一个正整数 $n$，表示点的数目。 第二行输入 $n$ 个以空格隔开的整数，依次表示各个点的点权 $a_i$。

输出一行一个整数，表示求得的最大点权和。

对于 $50\%$ 的数据满足 $n\le 18$； 对于 $100\%$ 的数据满足 $2\le n\le 10^5,|a_i|\le 10^9$。