题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

7
2 -2 8 6 -1 -5 5

样例输出 #1

13

提示

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