背景

STM向CYC表白前
SBW给STM出了一道题

描述

环上有N个数\(A_1\),\(A_2\),...,\(A_N\)
其中
\(A_i(1<=i<N)\)与\(A_{i+1}\)是相邻的
\(A_N\)与\(A_1\)是相邻的
在环上取数
相邻的数不可以都取
求取的数之和的最大值

输入

第一行一个正整数N
第二行N个正整数\(A_1\),\(A_2\),...,\(A_N\)

输出

一行一个正整数为所求值

样例1

输入

5
3 4 5 3 4

输出

9

样例2

输入

11
5 6 9 7 4 6 3 1 6 8 5

输出

30

范围

50% N<=20
70% N<=\(10^5\)
100% N<=\(10^6\) \(|A_i|\leq 1000\)

限制

1s
128M