题目描述

有一个长度为 $n$ 的环，每个元素的值为 $a_i$，求选择若干个元素，没有任意两个元素相邻，且元素和最大，输出这个最大值。

输入格式

第一行输入元素个数 $n$。

第二行输入 $n$ 个空格隔开的数字 $a_i$。

输出格式

输出一个最大值

7
2 -2 8 6 -1 -5 5

13

提示

$2\leq n\leq 10^5,|a_i|\leq 10^9$